Problem Description

Given the root of a binary tree original, a reference to a node target in the original tree, and the root of a clone of that tree cloned, you are to find the node in the cloned tree that corresponds to the target node in the original tree.

• The cloned tree is a deep copy of the original, so all values and structure are the same, but the nodes are different objects in memory.
• The function must return the reference (not just the value) to the corresponding node in the cloned tree.
• It is guaranteed that the target exists in the original tree and that there is exactly one valid answer.
• You cannot modify either tree or reuse any nodes between them.

The function signature may look like:
getTargetCopy(original, cloned, target)

Thought Process

At first glance, it might seem tricky to "find" a node in the cloned tree that matches the target node in the original tree, especially since the nodes are different objects in memory (even if their values are the same).

A brute-force approach would be to traverse the cloned tree and compare each node's value with the target's value. But this is not reliable if node values are not unique, since multiple nodes can have the same value.

Instead, we realize that since both trees are structurally identical and have the same values at each corresponding position, we can traverse both trees simultaneously. When we reach the target node in the original tree, the node we reach in the cloned tree at the same time is the answer.

This approach avoids ambiguity and ensures we find the exact corresponding node, regardless of value duplicates.

Solution Approach

The key idea is to traverse both the original and cloned trees in parallel. This can be done using depth-first search (DFS) or breadth-first search (BFS). Here are the steps:

1. Start at the root of both trees (original and cloned).
2. At each step, check if the current node in the original tree is the target node (compare by reference, not value).
3. If it is, return the current node in the cloned tree.
4. Otherwise, recursively (or iteratively) search the left and right children of both trees in parallel.
5. As soon as you find the target in the original, return the corresponding node in the cloned.

This approach guarantees that we find the corresponding node, even if values are duplicated, because we're matching structure and position, not value.

Example Walkthrough

Let's consider the following binary tree:

      7
     / \
    4   3
       / \
      6   19
  

• original is the root of this tree.
• cloned is an exact deep copy.
• target is the node with value 3 in original (the right child of the root).

As we traverse both trees in parallel:

1. Start at root (value 7): original is not target.
2. Traverse left child (value 4): still not target.
3. Traverse right child (value 3): this is target in original.
4. At this point, return the corresponding node in cloned (the right child of the cloned root).

The function returns the reference to the cloned node with value 3, which is at the same position as target.

Time and Space Complexity

• Brute-force approach: If you search the cloned tree for a node with the same value as target, the time complexity is O(N), but this is unreliable if there are duplicate values.
• Optimized approach (parallel traversal): In the worst case, you may have to traverse the entire tree to find target, so the time complexity is O(N), where N is the number of nodes in the tree.
• The space complexity is O(H), where H is the height of the tree, due to recursion stack (DFS) or queue (BFS). In the worst case (skewed tree), H can be O(N).

This is efficient and optimal for this problem.

Code Implementation

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def getTargetCopy(self, original, cloned, target):
        if original is None:
            return None
        if original is target:
            return cloned
        left = self.getTargetCopy(original.left, cloned.left, target)
        if left:
            return left
        return self.getTargetCopy(original.right, cloned.right, target)
      

// Definition for a binary tree node.
// struct TreeNode {
//     int val;
//     TreeNode *left;
//     TreeNode *right;
//     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
// };

class Solution {
public:
    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) return left;
        return getTargetCopy(original->right, cloned->right, target);
    }
};
      

// Definition for a binary tree node.
// public class TreeNode {
//     int val;
//     TreeNode left;
//     TreeNode right;
//     TreeNode(int x) { val = x; }
// }

class Solution {
    public final TreeNode getTargetCopy(final TreeNode original, final TreeNode cloned, final 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);
    }
}
      

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */

/**
 * @param {TreeNode} original
 * @param {TreeNode} cloned
 * @param {TreeNode} target
 * @return {TreeNode}
 */
var getTargetCopy = function(original, cloned, target) {
    if (original === null) return null;
    if (original === target) return cloned;
    let left = getTargetCopy(original.left, cloned.left, target);
    if (left !== null) return left;
    return getTargetCopy(original.right, cloned.right, target);
};
      

Summary

This problem demonstrates how synchronized traversal of two identical tree structures allows you to map references between them, independent of node values. By traversing both trees in parallel and comparing nodes by reference, you guarantee finding the corresponding node, even with duplicate values or complex structures. The solution is both simple and robust, leveraging the properties of deep copies and tree traversal fundamentals.