Find a Corresponding Node of a Binary Tree in a Clone of That Tree

You are given two binary trees, original and cloned, where cloned is a copy of original. You are also given a reference to a node target in the original tree. Return the corresponding node in the cloned tree (the node that occupies the same position).

This is LeetCode 1379: Find a Corresponding Node of a Binary Tree in a Clone of That Tree, and it is one of the cleanest problems for learning parallel tree traversal. The technique it teaches applies to any problem where you need to mirror your position across two identical structures.

Why this problem matters

Tree problems often involve traversing a single tree. This problem adds a twist: you traverse two trees at the same time, keeping your position synchronized. Every time you go left in the original, you go left in the clone. Every time you go right in the original, you go right in the clone. When you find the target in the original tree, the node you are currently visiting in the clone is the answer.

This "parallel traversal" idea appears whenever you need to compare two trees structurally (like Same Tree or Symmetric Tree) or when you need to find a corresponding position across a copied structure. Mastering it here makes those problems feel automatic.

The key insight

You do not need to search for a node by value. The problem gives you a reference to the target node, not a value. This means you compare nodes by identity (original is target), not by value. Two nodes might have the same value, but only one is the actual target.

The algorithm:

1. Start DFS at the root of both trees simultaneously.
2. At each step, check if the current node in the original tree is the target (reference comparison).
3. If yes, return the current node in the cloned tree.
4. Otherwise, recurse left on both trees. If the left subtree returns a result, pass it up.
5. If not found on the left, recurse right on both trees.

Because the trees are identical in structure, every move you make in the original has an exact mirror in the clone. When you arrive at the target in the original, you have arrived at the corresponding node in the clone.

The solution

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

def get_target_copy(original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:
    if original is None:
        return None
    if original is target:
        return cloned
    left = get_target_copy(original.left, cloned.left, target)
    if left:
        return left
    return get_target_copy(original.right, cloned.right, target)

Let's walk through what each piece does.

The base case handles None nodes. If we have gone past a leaf, there is nothing to return.

The identity check (original is target) is the core of the algorithm. We are not comparing values. We are checking whether this specific node object is the one we are looking for. When it matches, we return the corresponding cloned node, which is at the exact same position in the clone tree.

The recursive calls mirror our movement. original.left pairs with cloned.left, and original.right pairs with cloned.right. We try the left subtree first. If it returns a non-None result, the target was found on the left side and we pass it up. Otherwise, we try the right subtree.

Visual walkthrough

Let's trace through an example step by step. Watch how both trees are traversed in lockstep until the target is found in the original.

Notice that we never look at node values to decide if we found the target. We compare references. The DFS explores both trees in exactly the same order, and the moment we reach the target in the original, the cloned pointer is sitting on the answer.

Complexity analysis

Time is O(n) where n is the number of nodes in the tree. In the worst case, the target is the last node visited, so we traverse every node. Each node is visited at most once.

Space is O(h) where h is the height of the tree. This is the recursion stack depth. For a balanced tree, h = O(log n). For a completely skewed tree (essentially a linked list), h = O(n).

The building blocks

1. Parallel tree traversal

The pattern of traversing two trees simultaneously by moving left-left and right-right:

def traverse(node_a, node_b):
    if node_a is None:
        return
    process(node_a, node_b)
    traverse(node_a.left, node_b.left)
    traverse(node_a.right, node_b.right)

This is the foundation for comparing two trees (Same Tree), checking mirror symmetry (Symmetric Tree), and any problem where two structures must be walked in lockstep. The key is that both pointers advance together, so their positions always correspond.

2. DFS with early termination

The pattern of returning as soon as a condition is met, without visiting the rest of the tree:

def find(node):
    if node is None:
        return None
    if condition(node):
        return node
    left = find(node.left)
    if left:
        return left
    return find(node.right)

This short-circuits the search. Once the target is found in the left subtree, we skip the right subtree entirely. You see this pattern in problems like "Find a node with value X" or "Check if a path exists." The if left: return left guard is what prevents unnecessary work.

Edge cases

Before submitting, think through these scenarios:

• Target is the root: the first comparison succeeds immediately. Return cloned (the root of the clone tree).
• Target is a leaf: DFS traverses down to the leaf. The identity check matches at the deepest level. No children to recurse into afterward.
• Single node tree: the tree has only the root. Target must be the root. Return the cloned root.
• Skewed tree (linked list shape): all nodes are left children (or all right children). DFS degrades to a linear scan. Time is still O(n), but the recursion stack is O(n) deep.
• Target deep in the right subtree: the entire left subtree is traversed first before reaching the target on the right side. The early termination pattern ensures we stop as soon as the target is found.

From understanding to recall

You have seen how parallel DFS works: walk both trees in lockstep, compare references, and return the clone node when the original matches the target. The logic is minimal and the code is short. But reproducing it quickly in an interview is a different skill.

The details that cause mistakes are small. Do you compare with is or ==? Do you check original is None or cloned is None? Do you remember to check the return value of the left recursive call before trying right? These are recall gaps, not understanding gaps, and they cost time under pressure.

Spaced repetition is how you close them. You practice writing the parallel traversal, the identity check, and the early return pattern from memory at increasing intervals. After a few rounds, you see "find corresponding node" and the code writes itself.

Related posts

• Same Tree - The classic parallel tree traversal problem that compares two trees node by node
• Symmetric Tree - A mirror-image variant of parallel traversal where left pairs with right
• Maximum Depth of Binary Tree - The foundational recursive DFS pattern on a single tree

CodeBricks breaks this problem into its parallel traversal and early-termination building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a tree problem shows up in your interview, you do not think about it. You just write it.