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

Easy

#1278Time: O(N), where N is the number of nodes in the tree. In the worst case, the target node might be the last one visited in the traversal of the `cloned` tree.Space: O(H), where H is the height of the tree. This space is used by the recursion stack. In the worst case of a skewed tree, H can be N, making the space complexity O(N). For a balanced tree, it's O(log N).

Algorithms

Depth-First Search Breadth-First Search

Data structures

Tree Binary Tree

Prompt

Given two binary trees original and cloned and given 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 that you are not allowed to change any of the two trees or the target node and the answer must be a reference to a node in the cloned tree.

Example 1:

Input: tree = [7,4,3,null,null,6,19], target = 3
Output: 3
Explanation: In all examples the original and cloned trees are shown. The target node is a green node from the original tree. The answer is the yellow node from the cloned tree.

Example 2:

Input: tree = [7], target =  7
Output: 7

Example 3:

Input: tree = [8,null,6,null,5,null,4,null,3,null,2,null,1], target = 4
Output: 4

Constraints:

The number of nodes in the tree is in the range [1, 10⁴].
The values of the nodes of the tree are unique.
target node is a node from the original tree and is not null.

Follow up: Could you solve the problem if repeated values on the tree are allowed?

Approaches

2 approaches with complexity analysis and trade-offs.

This approach first finds the value of the target node in the original tree. Then, it performs a standard tree traversal (like pre-order, in-order, or BFS) on the cloned tree to find the node with the same value. This works only because the problem statement guarantees that all node values are unique.

Algorithm

Get the value of the target node, let's call it val.
Start a traversal on the cloned tree from its root. A recursive pre-order traversal is a common choice.
For each node visited in the cloned tree:
- Check if the node's value is equal to val.
- If it is, return this node.
If the traversal completes without finding the node, return null (though this won't happen based on problem constraints).

Walkthrough

The core idea is to use the target node's value as a unique identifier. Since the problem statement guarantees that all node values in the tree are unique, finding a node with the same value in the cloned tree is sufficient to locate the corresponding node.

The algorithm proceeds in two conceptual steps:

Retrieve the value of the target node: int targetValue = target.val;
Traverse the cloned tree. A recursive pre-order traversal is a straightforward way to implement this.
In the traversal function, for each visited node in the cloned tree, compare its value with targetValue.
If a match is found, that node is the answer, and we can return it, terminating the search.

1/**2 * Definition for a binary tree node.3 * public class TreeNode {4 *     int val;5 *     TreeNode left;6 *     TreeNode right;7 *     TreeNode(int x) { val = x; }8 * }9 */10 11class Solution {12    public final TreeNode getTargetCopy(final TreeNode original, final TreeNode cloned, final TreeNode target) {13        if (original == null) {14            return null;15        }16        // Use a helper function to search in the cloned tree by value17        return findNodeByValue(cloned, target.val);18    }19 20    private TreeNode findNodeByValue(TreeNode node, int value) {21        if (node == null) {22            return null;23        }24        if (node.val == value) {25            return node;26        }27        TreeNode leftResult = findNodeByValue(node.left, value);28        if (leftResult != null) {29            return leftResult;30        }31        return findNodeByValue(node.right, value);32    }33}

Complexity

Time

O(N), where N is the number of nodes in the tree. In the worst case, the target node might be the last one visited in the traversal of the `cloned` tree.

Space

O(H), where H is the height of the tree. This space is used by the recursion stack. In the worst case of a skewed tree, H can be N, making the space complexity O(N). For a balanced tree, it's O(log N).

Trade-offs

Pros

Conceptually simple and easy to implement.

Cons

This approach will fail if the tree contains duplicate node values, as it might return the wrong node. It is not a general solution and only works because of the specific constraint that values are unique.

This is a more robust approach that traverses both the original and cloned trees at the same time, in the same order (e.g., pre-order). By moving in lockstep through both trees, when we encounter the target node in the original tree, the current node in the cloned tree traversal is guaranteed to be its corresponding copy. This method works even if the tree contains duplicate values.

Algorithm

Define a recursive function, for example, findCorresponding(originalNode, clonedNode, target).
Base Case: If originalNode is null, it means we've reached the end of a branch without finding the target, so return null.
Check Target: Compare the originalNode reference with the target reference (originalNode == target). If they are the same object, it means we've found the target in the original tree. The corresponding node is clonedNode, so we return it.
Recurse Left: Call the function recursively for the left children: findCorresponding(originalNode.left, clonedNode.left, target). If this call returns a non-null node, it means the target was found in the left subtree. Propagate this result up by returning it immediately.
Recurse Right: If the left subtree search returned null, it means the target is in the right subtree. Call the function recursively for the right children: findCorresponding(originalNode.right, clonedNode.right, target) and return its result.
The initial call will be getTargetCopy(original, cloned, target).

Walkthrough

This method does not rely on node values, but on the identical structure of the two trees and the reference to the target node itself. We can use any standard traversal method (DFS like pre-order, in-order, post-order, or BFS) as long as we apply it to both trees simultaneously.

Let's use a recursive pre-order traversal. The recursive function will take the current node from the original tree and the current node from the cloned tree as arguments.

The base case for the recursion is when the current original node is null.

The main check inside the function is if (original_node == target). If this condition is true, we have found the node we are looking for in the original tree, so we can immediately return its counterpart, cloned_node.

If the current node is not the target, we continue the search by making recursive calls on the left children (original_node.left, cloned_node.left) and then the right children (original_node.right, cloned_node.right). The search is optimized to stop as soon as the target is found in either subtree.

1/**2 * Definition for a binary tree node.3 * public class TreeNode {4 *     int val;5 *     TreeNode left;6 *     TreeNode right;7 *     TreeNode(int x) { val = x; }8 * }9 */10 11class Solution {12    public final TreeNode getTargetCopy(final TreeNode original, final TreeNode cloned, final TreeNode target) {13        // Base case: if the current original node is null, we've reached the end of a path.14        if (original == null) {15            return null;16        }17 18        // Check if the current original node is the target node.19        // We compare by reference, not by value.20        if (original == target) {21            return cloned;22        }23 24        // Recursively search in the left subtree.25        TreeNode leftResult = getTargetCopy(original.left, cloned.left, target);26        // If the target was found in the left subtree, the result will not be null.27        // We can return it immediately without searching the right subtree.28        if (leftResult != null) {29            return leftResult;30        }31 32        // If not found in the left subtree, search in the right subtree.33        return getTargetCopy(original.right, cloned.right, target);34    }35}

Complexity

Time

O(N), where N is the number of nodes. We visit each node at most once. On average, if the target is randomly located, we'd visit N/2 nodes. The worst case is visiting N nodes if the target is the last node in the traversal order.

Space

O(H), where H is the height of the tree. This space is for the recursion stack. In the worst case of a skewed tree, this is O(N). For a balanced tree, it's O(log N).

Trade-offs

Pros

Correctly solves the problem even if node values are not unique, making it a robust and general solution.
It is efficient as it stops the traversal as soon as the target is found.
It directly addresses the problem by tracking the path to the target node structurally, rather than relying on potentially non-unique data.

Cons

The recursive implementation might lead to a stack overflow for very deep (skewed) trees, though this is unlikely given the constraint of 10^4 nodes. An iterative version using a stack can avoid this potential issue.

Solutions

Solution

1/** * Definition for a binary tree node. * public class TreeNode { * public int val; * public TreeNode left; * public TreeNode right; * public TreeNode(int x) { val = x; } * } */ public class Solution { private TreeNode target ; public TreeNode GetTargetCopy ( TreeNode original , TreeNode cloned , TreeNode target ) { this . target = target ; return dfs ( original , cloned ); } private TreeNode dfs ( TreeNode original , TreeNode cloned ) { if ( original == null ) { return null ; } if ( original == target ) { return cloned ; } TreeNode left = dfs ( original . left , cloned . left ); return left == null ? dfs ( original . right , cloned . right ) : left ; } }

1/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { private TreeNode target ; public final TreeNode getTargetCopy ( final TreeNode original , final TreeNode cloned , final TreeNode target ) { this . target = target ; return dfs ( original , cloned ); } private TreeNode dfs ( TreeNode root1 , TreeNode root2 ) { if ( root1 == null ) { return null ; } if ( root1 == target ) { return root2 ; } TreeNode res = dfs ( root1 . left , root2 . left ); return res == null ? dfs ( root1 . right , root2 . right ) : res ; } }

1/** * 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 ) { function < TreeNode * ( TreeNode * , TreeNode * ) > dfs = [ & ]( TreeNode * root1 , TreeNode * root2 ) -> TreeNode * { if ( root1 == nullptr ) { return nullptr ; } if ( root1 == target ) { return root2 ; } TreeNode * left = dfs ( root1 -> left , root2 -> left ); return left == nullptr ? dfs ( root1 -> right , root2 -> right ) : left ; }; return dfs ( original , cloned ); } };

1# 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 : TreeNode , cloned : TreeNode , target : TreeNode ) -> TreeNode : def dfs ( root1 : TreeNode , root2 : TreeNode ) -> TreeNode : if root1 is None : return None if root1 == target : return root2 return dfs ( root1 . left , root2 . left ) or dfs ( root1 . right , root2 . right ) return dfs ( original , cloned )

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem