This post is part of the Algorithms Problem Solving series.
Problem Description
This is the Clone Binary Tree problem. The description looks like this:
Given two binary trees original
and cloned
and given a reference to a node target
in the original tree.
The cloned
tree is a copy of the original
tree.
Return a reference to the same node in the cloned
tree.
Note that you are not allowed to change any of the two trees or the target
node and the answer must be a reference to a node in the cloned
tree.
Follow up: Solve the problem if repeated values on the tree are allowed.
Examples
Input: tree = [7,4,3,null,null,6,19], target = 3
Output: 3
Input: tree = [7], target = 7
Output: 7
Input: tree = [8,null,6,null,5,null,4,null,3,null,2,null,1], target = 4
Output: 4
Input: tree = [1,2,3,4,5,6,7,8,9,10], target = 5
Output: 5
Input: tree = [1,2,null,3], target = 2
Output: 2
Solution
The idea of my solution was to traverse the tree, starting from the left to the right side of the tree. To trsverse a tree, we use a recursion. The base case of this recursion is when we find the target value in the cloned tree. When we find it, just return the cloned tree node.
As I said earlier, we start from the left side of the tree. If we find it, the result will be different than None
, so we just return the node reference. We do the same thing for the right side of the tree.
def get_target_copy(original, cloned, target):
if cloned.val == target.val:
return cloned
if cloned.left:
result = get_target_copy(original.left, cloned.left, target)
if result:
return result
if cloned.right:
result = get_target_copy(original.right, cloned.right, target)
if result:
return result
Resources
- Learning Python: From Zero to Hero
- Algorithms Problem Solving Series
- Big-O Notation For Coding Interviews and Beyond
- Learn Python from Scratch
- Learn Object-Oriented Programming in Python
- Data Structures in Python: An Interview Refresher
- Data Structures and Algorithms in Python
- Data Structures for Coding Interviews in Python
- One Month Python Course
Top comments (0)