Skip to main content
Talentd

Find a Corresponding Node of a Binary Tree in a Clone of That Tree - Solution & Explanation

EasyTreeDepth-First SearchBreadth-First SearchBinary Tree14 min readAsked at: Meta
Practice this problem

Problem Statement

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, 104].
  • 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?

Approach Overview

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 1: Approach 1: Recursive DFS

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.

Code

PythonJavaC++CC#JavaScript

Python

Java

C++

C

C#

JavaScript

Complexity

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.

Try this approach in the editor →

Approach 2: Approach 2: Iterative BFS

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.

Code

PythonJavaC++CC#JavaScript

Python

Java

C++

C

C#

JavaScript

Complexity

Time Complexity: O(N)
Space Complexity: O(W), where W is the maximum width of the tree.

Try this approach in the editor →

Approach 3: DFS

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.

Code

PythonJavaC++TypeScriptC#

Python

Java

C++

TypeScript

C#

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Approach 1: Recursive DFS

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.

Approach 2: Iterative BFS

Time Complexity: O(N)
Space Complexity: O(W), where W is the maximum width of the tree.

DFS—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Recursive DFSO(n)O(h)Preferred interview solution; clean recursive traversal with minimal extra memory
Iterative BFSO(n)O(n)Useful when avoiding recursion or when using level-order traversal

Video Solution

Find a Corresponding Node of a Binary Tree in a Clone of That Tree | Live Coding | Leetcode - 1379 • Algorithms Made Easy • 5,667 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Find a Corresponding Node of a Binary Tree in a Clone of That Tree easy or hard?
This problem is classified as Easy on LeetCode with a high acceptance rate around 85 percent. The challenge mainly tests familiarity with binary tree traversal and understanding that the original and cloned trees share identical structure, allowing synchronized traversal to locate the corresponding node.
Find a Corresponding Node of a Binary Tree in a Clone of That Tree Python/Java solution
The Python and Java solutions typically implement either recursive DFS or iterative BFS. The DFS version checks if the current node equals the target and recursively searches left and right subtrees. Both implementations run in O(n) time and are concise because the original and cloned trees are traversed simultaneously.
How to solve Find a Corresponding Node of a Binary Tree in a Clone of That Tree in O(n)?
Traverse the original and cloned trees in parallel using DFS or BFS. Compare each visited node in the original tree with the target reference. When the target node is found, immediately return the corresponding node from the cloned tree. Because each node is processed once, the algorithm runs in O(n) time.
What is the best approach for Find a Corresponding Node of a Binary Tree in a Clone of That Tree?
The most common approach is a synchronized DFS traversal of both the original and cloned trees. Traverse both trees simultaneously and check whether the current node in the original tree matches the target reference. When a match is found, return the node from the cloned tree. This solution runs in O(n) time and O(h) space where h is the tree height.
Is Find a Corresponding Node of a Binary Tree in a Clone of That Tree asked at Google/Amazon/Meta?
Tree traversal problems like this frequently appear in technical interviews at large tech companies including Amazon, Google, and Meta. Interviewers often use variations involving binary tree traversal, cloning, or node mapping to test understanding of DFS, BFS, and pointer/reference handling.
What data structure is used in Find a Corresponding Node of a Binary Tree in a Clone of That Tree?
The primary data structure is a binary tree. The recursive solution uses the call stack to perform depth-first traversal, while the iterative solution uses a queue to perform breadth-first traversal. Both approaches rely on visiting nodes in the same structural order in both trees.
What is the time complexity of Find a Corresponding Node of a Binary Tree in a Clone of That Tree?
The time complexity is O(n) because every node in the binary tree may need to be visited once during traversal. Both DFS and BFS approaches scan the tree while maintaining alignment between the original and cloned trees. Space complexity is O(h) for recursive DFS due to the recursion stack or O(n) for BFS due to the queue.

Ready to solve this problem?

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 FleetCode
Previous

Binary Tree Inorder Traversal

Next

Unique Binary Search Trees II