Find a Corresponding Node of a Binary Tree in a Clone
Problem
You are given two binary trees: original and a cloned copy that is structurally identical to it. You also get a reference to one node, target, that belongs to the original tree. Return the node in the cloned tree that sits at the very same position as target. You may assume the values are not necessarily distinct, so you must rely on position rather than value.
original = "7, 4, 3, _, _, 6, 19", target = 33def get_target_copy(original, cloned, target):
if original is None:
return None
if original is target:
return cloned
left = get_target_copy(original.left, cloned.left, target)
if left is not None:
return left
return get_target_copy(original.right, cloned.right, target)function getTargetCopy(original, cloned, target) {
if (original === null) return null;
if (original === target) return cloned;
const left = getTargetCopy(original.left, cloned.left, target);
if (left !== null) return left;
return getTargetCopy(original.right, cloned.right, target);
}class Solution {
public TreeNode getTargetCopy(TreeNode original, TreeNode cloned, TreeNode target) {
if (original == null) return null;
if (original == target) return cloned;
TreeNode left = getTargetCopy(original.left, cloned.left, target);
if (left != null) return left;
return getTargetCopy(original.right, cloned.right, target);
}
}TreeNode* getTargetCopy(TreeNode* original, TreeNode* cloned, TreeNode* target) {
if (original == nullptr) return nullptr;
if (original == target) return cloned;
TreeNode* left = getTargetCopy(original->left, cloned->left, target);
if (left != nullptr) return left;
return getTargetCopy(original->right, cloned->right, target);
}Explanation
The cloned tree is a perfect copy of original — same shape, same arrangement — just made of different node objects. So the node we want lives at the exact same position in the clone as target does in the original. The trick is to walk both trees together, step for step.
We descend the two trees in lockstep: whenever we move to the left child in original, we move to the left child in cloned too; same for the right. At every step the two pointers are always looking at matching positions.
The moment the original pointer is the same object as target (an identity check, not a value check), the cloned pointer is sitting on the answer — so we return it. If we ever run off the tree (a null), we return null and let the search continue elsewhere.
Because values can repeat, we deliberately compare node references, not values. That is why original is target (Python) / original === target (JS) / original == target (Java & C++) is the right test.
Example: original = [7, 4, 3, _, _, 6, 19] with target being the node valued 3. From the root 7 we check left subtree first (the 4 branch), find nothing, then check the right child — that node is target, so we return the clone's node at that spot, which also holds 3.