Problem Description

You are given two binary trees: original and cloned. The cloned tree is an exact copy of the original tree with the same structure and node values. You are also given a reference to a specific node called target that exists in the original tree.

Your task is to find and return a reference to the corresponding node in the cloned tree that matches the target node from the original tree.

The key constraints are:

• You cannot modify either tree
• You cannot modify the target node
• Your answer must be a reference to the actual node in the cloned tree, not just a node with the same value

Since the cloned tree has the exact same structure as the original tree, the corresponding node will be at the same position in the cloned tree as the target node is in the original tree.

For example, if the target node is the left child of the root in the original tree, then you need to return the left child of the root in the cloned tree.

The solution uses a depth-first search (DFS) approach to traverse both trees simultaneously. When the traversal finds the target node in the original tree, it returns the corresponding node from the cloned tree at the same position. The function explores both left and right subtrees recursively until it finds the match.

Flowchart Walkthrough

First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:

Is it a graph?

• Yes: A binary tree is a special type of graph where each node has at most two children and there are no cycles.

Is it a tree?

• Yes: The problem explicitly states we're working with binary trees (original and cloned).

DFS

• Since we answered "yes" to the tree question, the flowchart leads us directly to DFS (Depth-First Search).

Conclusion: The flowchart suggests using DFS for this problem.

This makes perfect sense for our problem because:

1. We need to traverse two trees simultaneously (original and cloned)
2. We need to maintain the correspondence between nodes in both trees as we traverse
3. When we find the target node in the original tree, we can immediately return the corresponding node from the cloned tree
4. DFS allows us to explore each path deeply, checking if the current node in original matches target, and returning the corresponding cloned node if it does

The DFS approach naturally maintains the structural correspondence between the two trees as we traverse them in parallel, making it the ideal algorithm for finding the corresponding node in the cloned tree.

Intuition

The key insight is that the cloned tree has the exact same structure as the original tree. This means that if we traverse both trees in the same way at the same time, we'll always be at corresponding positions in both trees.

Think of it like having two identical mazes and walking through them step-by-step in sync. If you turn left in the first maze, you turn left in the second maze. If you go straight in the first maze, you go straight in the second maze. When you reach your destination in the first maze, you'll be at the corresponding location in the second maze.

This parallel traversal approach naturally emerges when we consider:

1. We can't compare nodes by value alone (there might be duplicate values)
2. We need to find the exact node object reference, not just a similar node
3. The position of the target node in the original tree directly maps to the position of its corresponding node in the cloned tree

The solution becomes elegantly simple: traverse both trees simultaneously using DFS. At each step, we're looking at two nodes - one from original and one from cloned that are at the same structural position. When we find that the current node in original is our target, we know that the current node in cloned is exactly what we're looking for.

The beauty of this approach is that we don't need to store any path information or node mappings. The recursive DFS naturally maintains the correspondence between nodes as we explore the trees. If we go left in original, we go left in cloned. If we go right in original, we go right in cloned. This synchronized movement guarantees that when we find target in original, we're standing at its twin in cloned.

Learn more about Tree, Depth-First Search, Breadth-First Search and Binary Tree patterns.

Solution Approach

The implementation uses a recursive DFS helper function dfs(root1, root2) that traverses both trees simultaneously. Here's how it works:

Function Structure: The dfs function takes two parameters:

• root1: Current node in the original tree
• root2: Corresponding node in the cloned tree

Base Case:

if root1 is None:
    return None

If we reach a null node in the original tree, there's nothing to search, so we return None.

Target Found:

if root1 == target:
    return root2

This is the key moment - when we find that the current node in original is the target node, we immediately return the corresponding node root2 from the cloned tree. Since we've been traversing both trees in sync, root2 is guaranteed to be at the same structural position as target.

Recursive Exploration:

return dfs(root1.left, root2.left) or dfs(root1.right, root2.right)

If the current node isn't the target, we recursively search both subtrees:

• First, we explore the left subtrees of both trees together
• Then, we explore the right subtrees of both trees together

The or operator is clever here - it returns the first non-None result. If the target is found in the left subtree, that result is returned immediately without exploring the right subtree (short-circuit evaluation). If the left subtree returns None, then we check the right subtree.

Time Complexity: O(n) where n is the number of nodes, as we might need to visit every node in the worst case.

Space Complexity: O(h) where h is the height of the tree, representing the recursion stack depth. In the worst case of a skewed tree, this could be O(n).

The elegance of this solution lies in its simplicity - by maintaining synchronized traversal of both trees, we automatically preserve the structural correspondence between nodes without any additional bookkeeping.

Example Walkthrough

Let's walk through a concrete example to see how the solution works.

Consider these two identical trees where we need to find the node with value 3 (marked with *) in the cloned tree:

Original Tree:        Cloned Tree:
      7                    7
     / \                  / \
    3*  4                3   4
   /   / \              /   / \
  2   6   9            2   6   9

Our target is the node with value 3 in the original tree (left child of root).

Step-by-step traversal:

1. Start at roots: dfs(original:7, cloned:7)

   • Is original:7 == target:3? No
   • Explore left subtree: dfs(original:3, cloned:3)

2. At left children: dfs(original:3, cloned:3)

   • Is original:3 == target:3? Yes!
   • Return cloned:3 ← This is our answer

The function returns immediately when we find the target. We never even explore the right subtree of the root because the or operator short-circuits when the left recursion returns a non-None value.

What if the target was deeper in the tree? Let's say target is the node with value 6:

Original Tree:        Cloned Tree:
      7                    7
     / \                  / \
    3   4                3   4
   /   / \              /   / \
  2   6*  9            2   6   9

The traversal would proceed as:

1. dfs(7, 7) - Not target, explore left
2. dfs(3, 3) - Not target, explore left
3. dfs(2, 2) - Not target, no children, return None
4. Back to step 2, explore right: dfs(None, None) - Returns None
5. Back to step 1, left returned None, explore right: dfs(4, 4) - Not target
6. dfs(6, 6) - Found target! Return cloned:6

The synchronized traversal ensures that when we find node 6 in the original tree, we're at the corresponding node 6 in the cloned tree, maintaining the exact structural position throughout the search.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n)

The algorithm performs a depth-first search (DFS) traversal on both trees simultaneously. In the worst case, we need to visit every node in the tree before finding the target node (or the target could be the last node visited). Since we visit each node at most once, the time complexity is O(n), where n is the number of nodes in the tree.

Space Complexity: O(n)

The space complexity is determined by the recursive call stack. In the worst case, the tree could be completely unbalanced (essentially a linked list), where each node has only one child. This would result in a recursion depth equal to the number of nodes n, giving us O(n) space complexity. In the best case of a perfectly balanced tree, the recursion depth would be O(log n), but we consider the worst-case scenario for complexity analysis.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Comparing Node Values Instead of Node References

The Problem: A common mistake is comparing node values (root1.val == target.val) instead of node references (root1 == target). This would be incorrect because multiple nodes might have the same value, and we need to find the exact corresponding node, not just any node with the same value.

Incorrect Implementation:

# WRONG: This compares values, not references
if root1.val == target.val:
    return root2

Why This Fails: Consider a tree where multiple nodes have the value 5. If the target is the second occurrence of 5, comparing values would incorrectly return the first node with value 5 in the cloned tree.

Correct Implementation:

# CORRECT: This compares object references
if root1 == target:
    return root2

Pitfall 2: Not Handling the Short-Circuit Properly

The Problem: Using just or without understanding its behavior, or incorrectly implementing the recursive calls can lead to missing the target node.

Incorrect Implementation:

# WRONG: This always explores both subtrees
left_result = dfs(root1.left, root2.left)
right_result = dfs(root1.right, root2.right)
return left_result or right_result

Why This is Inefficient: While this works, it unnecessarily explores the entire right subtree even when the target is found in the left subtree, wasting computational resources.

Better Implementation:

# Efficient: Short-circuits when target is found
return dfs(root1.left, root2.left) or dfs(root1.right, root2.right)

# Or explicitly with early return:
left_result = dfs(root1.left, root2.left)
if left_result:
    return left_result
return dfs(root1.right, root2.right)

Pitfall 3: Traversing Only One Tree

The Problem: Beginners might try to find the target in the original tree first, then separately traverse the cloned tree to find the corresponding node. This requires additional logic to track the path or position.

Incorrect Approach:

# WRONG: Trying to find path first, then apply it
def getTargetCopy(self, original, cloned, target):
    # Find path to target in original
    path = self.findPath(original, target)
    # Apply path to cloned tree
    return self.followPath(cloned, path)

Why This is Complex: This approach requires maintaining path information and implementing two separate functions, making the solution unnecessarily complicated.

Correct Approach: Traverse both trees simultaneously, maintaining the structural correspondence naturally through synchronized recursion.