---

1. Problem Summary

You are given:

• The root of a binary tree
• A separate cloned copy of the same tree called cloned
• A specific node reference from the original tree called target

Your task is to:

Return the node in the cloned tree that corresponds to the target node in the original tree.

Important details:

• Node values may not be unique
• You must match using node identity, not value comparison
• Tree structure in both trees is identical
• Both trees contain the target node at the same structural position

The output must be a reference to the matching node in the cloned tree.

---

2. Key Insights

Value comparison is not reliable

Because multiple nodes can have the same value, we must not return the first matching value.

Tree structure is identical in both original and cloned trees

Meaning corresponding nodes appear at the exact mirrored traversal positions.

Traversal simultaneously across both trees works

If we traverse original and cloned trees in the same order:

• When original visitation reaches target
• the cloned traversal is visiting the corresponding node

DFS or BFS both work

Any traversal style (preorder, inorder, postorder, BFS) is valid as long as both trees are traversed in sync.

Once found, no further traversal is required

Return immediately to avoid unnecessary extra processing.

---

3. Approach

Synchronized DFS Traversal

Steps:

1. If original node is null → return null
2. If original node is the target:
   return cloned node
3. Recursively search left subtree: result = dfs(original.left, cloned.left) if result != null return result
4. Recursively search right subtree: return dfs(original.right, cloned.right)

This guarantees that when original hits target, cloned is aligned.

---

4. Time and Space Complexity

Time Complexity: O(N)

You may visit all nodes in worst case.

Space Complexity:

• O(H) recursion stack depth
• worst case skewed tree → O(N)
• balanced tree → O(log N)

---

5. Java Solution

/**
 * 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 leftResult = getTargetCopy(original.left, cloned.left, target);
        if (leftResult != null) {
            return leftResult;
        }

        return getTargetCopy(original.right, cloned.right, target);
    }
}

---

6. Dry Run Examples

Example 1

Original and cloned:

      7
     / \
    4   3
       / \
      6   19

Target = reference to node 3 in original

Traversal:

• visit 7 → not match
• traverse left (4) → not match
• backtrack
• traverse right (3) → match found

Corresponding cloned node returned.

Output:

node in cloned tree with value 3 at same location

---

Example 2

Target is leaf

Tree:

  2
 / \
1   3

target refers to node 1

Traversal sequence:
2 → left → 1 (match)

Output:

cloned node with value 1

---

Example 3

Duplicate values

Original:

    5
   / \
  4   5

Cloned:

    5
   / \
  4   5

target is right child 5

Value alone ambiguous, but identity match ensures we return correct cloned 5.

---

Example 4

Target is root

Return cloned root immediately.

---

Example 5

Deeply nested target

Traversal continues until exact mirrored position is found.

---

7. Why This Solution Works

• Traverses both trees in perfect synchronization
• Uses identity matching, not value comparison
• Works for duplicate values
• Guaranteed to find exactly one corresponding node
• Does not modify trees
• Efficient and minimal logic

---

8. Common Mistakes

1. Matching by value instead of node identity
2. Searching only one tree and returning value
3. Assuming values unique when they are not
4. Using indexing or array representation
5. Forgetting to return early after finding match