Watch 10 video solutions for Find a Corresponding Node of a Binary Tree in a Clone of That Tree, a easy level problem involving Tree, Depth-First Search, Breadth-First Search. This walkthrough by Algorithms Made Easy has 5,633 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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:
tree is in the range [1, 104].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?
Problem Overview: You are given two binary trees: the original tree and its exact clone. A reference to a target node exists in the original tree. Your task is to locate and return the corresponding node in the cloned tree. The trees have identical structure and values, but you must return the node from the cloned tree, not the original.
Approach 1: Recursive DFS (O(n) time, O(h) space)
This approach performs a synchronized depth-first traversal on both trees at the same time. Start at the roots of the original and cloned trees. If the current node in the original tree matches the target reference, return the corresponding node from the cloned tree. Otherwise, recursively search the left subtree, then the right subtree. Because both trees share the same structure, traversing them in parallel guarantees that when you reach the target node in the original tree, the corresponding node in the clone is at the same traversal position. Time complexity is O(n) since every node may be visited once. Space complexity is O(h) due to the recursion stack, where h is the tree height. This solution relies on concepts from Depth-First Search and Binary Tree traversal.
Approach 2: Iterative BFS (O(n) time, O(n) space)
The iterative solution uses a queue to perform a level-order traversal of both trees simultaneously. Push the root nodes of the original and cloned trees into the queue as a pair. Repeatedly dequeue a pair and check if the original node equals the target reference. If it does, return the cloned node from the pair. Otherwise, enqueue the left children and right children from both trees together. This keeps traversal aligned between the trees. The algorithm processes each node at most once, giving O(n) time complexity, while the queue may store up to a full level of nodes, resulting in O(n) space complexity. This approach demonstrates classic Breadth-First Search traversal.
Recommended for interviews: Recursive DFS is usually the expected solution because it is concise and clearly demonstrates understanding of tree traversal. Iterative BFS is equally correct and sometimes preferred when recursion depth might become large. Showing the DFS version first proves you understand how to traverse trees, while mentioning the BFS alternative shows breadth of problem-solving strategies.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recursive DFS | O(n) | O(h) | Preferred interview solution; clean recursive traversal with minimal extra memory |
| Iterative BFS | O(n) | O(n) | Useful when avoiding recursion or when using level-order traversal |