{x}
blog image

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

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?

Solution Explanation: Finding a Corresponding Node in a Cloned Binary Tree

This problem involves finding a corresponding node in a cloned binary tree given a target node in the original tree. The solution uses Depth-First Search (DFS) to efficiently traverse both trees simultaneously.

Approach:

The core idea is to recursively traverse both the original and cloned trees in parallel. At each step, we compare the current node in the original tree with the target node. If they match, we've found the corresponding node in the cloned tree and return it. Otherwise, we recursively call the function on the left and right subtrees of both trees. If a match is found in either subtree, that result is returned; otherwise, null is returned to indicate no match in that subtree.

Algorithm:

  1. Base Case: If the current node in the original tree (root1) is null, it means we've reached the end of that branch, so we return null.

  2. Match Found: If root1 is equal to the target node, we've found the corresponding node in the original tree. The corresponding node in the cloned tree (root2) is then returned.

  3. Recursive Search: If neither of the above conditions is met, we recursively search the left and right subtrees. The function dfs is called recursively on both the left subtrees (root1.left, root2.left) and right subtrees (root1.right, root2.right).

  4. Combining Results: The results of the recursive calls are combined using a logical OR (|| in JavaScript/TypeScript, or in Python, ? : in Java/C#, || in C++). This ensures that if a match is found in either the left or right subtree, that node is returned immediately. Otherwise, if no match is found in either subtree, null is returned.

Time and Space Complexity Analysis:

  • Time Complexity: O(N), where N is the number of nodes in the tree. In the worst case, we might have to traverse all nodes in the tree to find the target node. This is because DFS visits each node exactly once.

  • Space Complexity: O(H), where H is the height of the tree. This is due to the recursive call stack. In the worst-case scenario (a skewed tree), the height could be equal to N, resulting in O(N) space complexity. However, for balanced trees, the height is typically log₂(N), making the space complexity O(log₂(N)).

Code Examples (Multiple Languages):

The code examples in Python, Java, C++, TypeScript, and C# demonstrate the implementation of the DFS approach. All these implementations follow the algorithm described above. Note that the code assumes a standard binary tree node definition is available in each language. The comments in the code further explain the specific steps.

Follow-up:

The follow-up question asks if we can solve this problem with repeated values in the tree. The provided solution would still work correctly, even with repeated values. The dfs function would still find a corresponding node, however, if you require all corresponding nodes then you would need to modify the return type to an array and append to that array during recursion. But for this problem, we only need to return one.