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?
In #1379 Find a Corresponding Node of a Binary Tree in a Clone of That Tree, you are given two binary trees: the original tree and its exact clone. The goal is to locate the node in the cloned tree that corresponds to a given target node in the original tree.
A common strategy is to traverse both trees simultaneously. Since the cloned tree has the exact same structure as the original, every step taken in the original tree can be mirrored in the clone. During traversal, whenever the current node in the original tree matches the target, the corresponding node in the cloned tree is the answer.
This can be implemented using either Depth-First Search (DFS) or Breadth-First Search (BFS). DFS recursively explores left and right children, while BFS processes nodes level by level using a queue. Both approaches ensure that nodes are visited in corresponding order in the two trees. The traversal takes O(n) time since each node may be visited once, with space complexity depending on recursion depth or queue usage.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Depth-First Search (DFS) | O(n) | O(h) where h is tree height |
| Breadth-First Search (BFS) | O(n) | O(n) in worst case due to queue |
Algorithms Made Easy
This approach involves using a recursive depth-first search to simultaneously traverse both the original and cloned trees. When you find the target node in the original tree, return the corresponding node in the cloned tree.
Time Complexity: O(N), where N is the number of nodes in the tree because each node is visited once.
Space Complexity: O(H), where H is the height of the tree due to the recursion stack.
1var getTargetCopy = function(original, cloned, target) {
2 if (original === null) return null;
3 if (original ===The JavaScript function performs a recursive search, return the cloned node matching the target node's position.
Utilizing a queue, this approach explores both the original and cloned trees in parallel level-by-level. Once the target node is located in the original tree, the corresponding node in the cloned tree is returned.
Time Complexity: O(N)
Space Complexity: O(W), where W is the maximum width of the tree.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Traversing both trees together ensures that we always maintain positional alignment between the original and cloned trees. Since their structures are identical, visiting nodes in the same order guarantees that the matching node in the clone is found when the target is encountered.
This problem represents a classic binary tree traversal pattern often seen in coding interviews. While the exact question may vary, the concept of synchronized traversal and tree comparison is commonly tested in FAANG-style interviews.
Binary trees are the core data structure in this problem. Depending on the traversal method, recursion (for DFS) or a queue (for BFS) is used to keep track of corresponding nodes in both trees.
The optimal approach is to traverse the original and cloned trees simultaneously using DFS or BFS. When the node in the original tree matches the target node, the corresponding node in the cloned tree is returned. This method leverages the identical structure of both trees.
JavaScript's getTargetCopy function leverages an array to both store node pairs and perform BFS by shifting from the queue-like array.