Skip to main content

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

Difficulty: Easy | Pattern: Tree DFS | Company tags: Amazon, Facebook

Problem Statement​

Given two binary trees original and cloned and a reference to a node target in the original tree.

The cloned tree is a copy of the original tree.

Return a reference to the same node in the cloned tree.

Note: You may not modify either tree or the target node. The answer is guaranteed to exist.

Example:

Input: tree = [7,4,3,null,null,6,19], target = 3
Output: reference to node 3 in the cloned tree

Algorithm Flow​

Approach: Simultaneous DFS — O(n)​

Key insight: Traverse both trees simultaneously. When the original node matches target, return the corresponding cloned node (same position in the tree).

def getTargetCopy(original, cloned, target):
    if not original:
        return None
    if original is target:
        return cloned
    
    # Search left subtree
    left = getTargetCopy(original.left, cloned.left, target)
    if left:
        return left
    
    # Search right subtree
    return getTargetCopy(original.right, cloned.right, target)

Iterative BFS Version​

from collections import deque

def getTargetCopy(original, cloned, target):
    queue = deque([(original, cloned)])
    while queue:
        orig, clone = queue.popleft()
        if orig is target:
            return clone
        if orig.left:
            queue.append((orig.left, clone.left))
        if orig.right:
            queue.append((orig.right, clone.right))
    return None

Why is Not ==​

original is target checks object identity (same object in memory), not just equal value. This is correct since target is a reference to a specific node, not just a value.

Edge Cases​

  • Target is root → immediate return
  • Target is a leaf → found at maximum depth
  • Tree with duplicate values → is identity check ensures correct node found

Complexity​

  • Time: O(n) — worst case visits all nodes
  • Space: O(h) — recursion depth; O(n) BFS queue

Key Terms​

TermDefinition
Simultaneous traversalWalking two structurally identical trees in lockstep so corresponding nodes are visited together
Object identity (is)Comparing memory references rather than values, needed to find the exact node, not just an equal one
DFS (depth-first search)Traversal that fully explores one subtree before backtracking to the next
BFS (breadth-first search)Level-by-level traversal using a queue, an alternative to recursion here

FAQ​

Q: Why use is instead of == to compare nodes? A: target is a reference to a specific node object in original. If node values could repeat, == (or comparing .val) could match the wrong node with the same value; is guarantees we find the exact node.

Q: Can this be solved iteratively? A: Yes — the BFS version above (or an iterative DFS using an explicit stack of (original, cloned) pairs) avoids recursion and its stack depth limits.

Q: What if the tree is very unbalanced (skewed)? A: Recursive DFS then costs O(n) stack depth in the worst case, which risks a stack overflow on very large skewed trees; the BFS/iterative approach avoids this by using heap-allocated queue/stack storage instead.

Q: Does this work if node values are not unique? A: Yes, precisely because we compare object identity (original is target) rather than value, duplicate values elsewhere in the tree don't cause false matches.

Q: Could this be solved without touching the cloned tree structure directly? A: An alternative is to record the path (sequence of left/right moves) from original's root to target during one traversal, then replay that same path on cloned to reach the corresponding node — useful if the two traversals can't be done simultaneously.

Quick Revision​

  • Pattern: simultaneous DFS/BFS over two structurally identical trees.
  • Traverse original and cloned in lockstep, moving into .left/.right together.
  • Base case: if original is target, return the paired cloned node.
  • Use is (identity), not == (value), to handle duplicate values correctly.
  • DFS: recurse left first, return if found, else recurse right.
  • BFS: queue pairs (orig, clone), dequeue and compare, then push children pairs.
  • Time O(n) worst case; Space O(h) for DFS recursion or O(n) for BFS queue.
  • Edge cases: target at root, target as a leaf, duplicate-valued tree.