This post is part of the Algorithms Problem Solving series.
This is the Clone Binary Tree problem. The description looks like this:
Given two binary trees
cloned and given a reference to a node
target in the original tree.
cloned tree is a copy of the
Return a reference to the same node in the
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
Follow up: Solve the problem if repeated values on the tree are allowed.
Input: tree = [7,4,3,null,null,6,19], target = 3 Output: 3 Input: tree = , 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
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
- 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