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.
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.
The function getTargetCopy checks if the current node in the original tree is the target. If so, it returns the corresponding node in the cloned tree. Otherwise, it recursively searches the left subtree, then the right subtree.
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.
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.
This getTargetCopy function uses a queue to iteratively traverse the trees. It dequeues a pair of nodes, checks the original against the target, and enqueues children if necessary.
Time Complexity: O(N)
Space Complexity: O(W), where W is the maximum width of the tree.
We design a function dfs(root1, root2), which performs DFS traversal simultaneously in trees root1 and root2. When traversing to a node, if this node happens to be target, then we return the corresponding node in root2. Otherwise, we recursively search for target in the left and right subtrees of root1 and root2, and return the result that is not empty.
The time complexity is O(n), and the space complexity is O(n). Where n is the number of nodes in the tree.
Python
Java
C++
TypeScript
C#
| Approach | Complexity |
|---|---|
| Approach 1: Recursive DFS | Time Complexity: O(N), where N is the number of nodes in the tree because each node is visited once. |
| Approach 2: Iterative BFS | Time Complexity: O(N) |
| DFS | — |
| 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 |
Find a Corresponding Node of a Binary Tree in a Clone of That Tree | Live Coding | Leetcode - 1379 • Algorithms Made Easy • 5,633 views views
Watch 9 more video solutions →Practice Find a Corresponding Node of a Binary Tree in a Clone of That Tree with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor