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

Problem

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.

Examples

Example 1:

graph LR
    subgraph Original
        H(7) --- E(4)
        H(7) --- D(3):::green
        D(3) --- F(6)
        D(3) --- T(19)
    end
    
    subgraph Cloned
        H'(7) --- E'(4)
        H'(7) --- D'(3):::yellow
        D'(3) --- F'(6)
        D'(3) --- T'(19)
        
    end

Original ~~~ Cloned
classDef green fill:#3CB371,stroke:#000,stroke-width:1px,color:#fff; 
classDef yellow fill:#FFD700,stroke:#000,stroke-width:1px,color:#000;

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:

graph LR
    subgraph Original
        H(7):::green
    end
    
    subgraph Cloned
        H'(7):::yellow
    end

Original ~~~ Cloned
classDef green fill:#3CB371,stroke:#000,stroke-width:1px,color:#fff;
classDef yellow fill:#FFD700,stroke:#000,stroke-width:1px,color:#000;

Input: tree = [7], target =  7
Output: 7

Example 3:

graph LR
    subgraph Original
        H(8)
        H(8) ~~~ N1:::hidden
        H --- G(6)
        G(6) ~~~ N2:::hidden
        G --- F(5)
        F(5) ~~~ N2:::hidden
        F --- E(4):::green
        E(4) ~~~ N3:::hidden
        E --- D(3)
        D(3) ~~~ N4:::hidden
        D --- C(2)
        C(2) ~~~ N5:::hidden
        C --- B(1)
    end
    
    subgraph Cloned
        H'(8)
        H'(8) ~~~ N1':::hidden
        H' --- G'(6)
        G'(6) ~~~ N2':::hidden
        G' --- F'(5)
        F'(5) ~~~ N2':::hidden
        F' --- E'(4):::yellow
        E'(4) ~~~ N3':::hidden
        E' --- D'(3)
        D'(3) ~~~ N4':::hidden
        D' --- C'(2)
        C'(2) ~~~ N5':::hidden
        C' --- B'(1)
    end

Original ~~~ Cloned
classDef green fill:#3CB371,stroke:#000,stroke-width:1px,color:#fff;
classDef yellow fill:#FFD700,stroke:#000,stroke-width:1px,color:#000;
classDef hidden display:none

Input: tree = [8,null,6,null,5,null,4,null,3,null,2,null,1], target = 4
Output: 4

Follow up

Could you solve the problem if repeated values on the tree are allowed?

Solution

We can do both BFS and DFS. With DFS, we can easily handle the follow up as well.

Method 1 - BFS

Instead of traversing the trees recursively (DFS), we can use an iterative approach with Breadth-First Search (BFS). BFS utilises a queue to simultaneously traverse both the original and cloned trees level-by-level. At each level, check whether the current node in the original tree matches the target node. If yes, return the corresponding node from the cloned tree.

BFS Approach

1. Use queues to store nodes from the original and its corresponding node from the cloned tree.
2. Start by adding the roots of both trees to their respective queues.
3. Dequeue nodes from the original and cloned queues one-by-one, and:
   • If the node from the original tree matches target, return the corresponding node from the cloned tree.
   • Add the left and right children of the dequeued nodes to the respective queues.
4. Repeat until the target node is found.

Code

Java

class Solution {
    public final TreeNode getTargetCopy(final TreeNode original, final TreeNode cloned, final TreeNode target) {
        // Initialize queues for BFS traversal
        Queue<TreeNode> qOriginal = new LinkedList<>();
        Queue<TreeNode> qCloned = new LinkedList<>();
        
        qOriginal.add(original);
        qCloned.add(cloned);
        
        while (!qOriginal.isEmpty()) {
            TreeNode currOriginal = qOriginal.poll();
            TreeNode currCloned = qCloned.poll();
            
            // If we find the target node
            if (currOriginal == target) {
                return currCloned;
            }
            
            // Add left children to both queues
            if (currOriginal.left != null) {
                qOriginal.add(currOriginal.left);
                qCloned.add(currCloned.left);
            }
            
            // Add right children to both queues
            if (currOriginal.right != null) {
                qOriginal.add(currOriginal.right);
                qCloned.add(currCloned.right);
            }
        }
        
        return null; // This point should not be reached
    }
}

Python

class Solution:
    def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> Optional[TreeNode]:
        # Initialize queues for BFS traversal
        q_original = deque([original])
        q_cloned = deque([cloned])
        
        while q_original:
            curr_original = q_original.popleft()
            curr_cloned = q_cloned.popleft()
            
            # If we find the target node
            if curr_original is target:
                return curr_cloned
            
            # Add left children to both queues
            if curr_original.left:
                q_original.append(curr_original.left)
                q_cloned.append(curr_cloned.left)
            
            # Add right children to both queues
            if curr_original.right:
                q_original.append(curr_original.right)
                q_cloned.append(curr_cloned.right)
        
        return None  # This point should not be reached

Complexity

• ⏰ Time complexity: O(n), as every node is visited once.
• 🧺 Space complexity: O(n). The maximum size of the queue can be n/2 (in the worst case when the tree is balanced, the last level has half the nodes).

Method 2 - DFS

We can use DFS traversal on both trees simultaneously and compare the current node from the original tree with the target node.

Base case

• If original is null, return null, since cloned will also be null at that moment.
• If original matches the target, return cloned, as it is the corresponding node. Other case
• Otherwise, search recursively on both sides to locate the target.

Code

Java

class Solution {
    public final TreeNode getTargetCopy(final TreeNode original, final TreeNode cloned, final TreeNode target) {
        if (original == null) {
	        return null;  // Base case
	    }
        
        if (original == target) {
	        return cloned;  // Found the target
	    }
        
        // Search in left subtree
        TreeNode ans = getTargetCopy(original.left, cloned.left, target);
        if (ans != null) {
	        return ans;
	    }
        
        // Search in right subtree
        return getTargetCopy(original.right, cloned.right, target);
    }
}

Python

class Solution:
    def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> Optional[TreeNode]:
        if not original:
            return None  # Base case
        
        if original is target:
            return cloned  # Found the target
        
        # Search in left subtree
        ans = self.getTargetCopy(original.left, cloned.left, target)
        if ans:
            return ans
        
        # Search in right subtree
        return self.getTargetCopy(original.right, cloned.right, target)

Complexity

• ⏰ Time complexity: O(n), as we may need to visit every node in the binary tree in the worst-case scenario.
• 🧺 Space complexity: O(h). The space required is determined by the recursive call stack, where h is the height of the tree. For a balanced binary tree, h = O(log n); for a skewed tree, h = O(n).