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.

Approach 1: DFS: Recursive Inorder Traversal.

class Solution {
    TreeNode ans, target;
    
    public void inorder(TreeNode o, TreeNode c) {
        if (o != null) {
            inorder(o.left, c.left);
            if (o == target) {
                ans = c;    
            }
            inorder(o.right, c.right);    
        }
    }
    
    public final TreeNode getTargetCopy(final TreeNode original, final TreeNode cloned, final TreeNode target) {
        this.target = target;
        inorder(original, cloned);
        return ans;
    }
}
                

Time Complexity: O(n) and Space Complexity: O(n)

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

This problem is an interesting application of tree traversal techniques and highlights the relationship between a binary tree and its exact clone.

Problem Statement

You are given the root of a binary tree and a node within the tree called target. You are also given a cloned version of this binary tree. The task is to locate and return the corresponding node in the cloned tree that matches the target node in the original tree.

Key Points to Note:

• The cloned binary tree is an exact copy of the original tree, including structure and node values.
• We are guaranteed that the target node exists in the original binary tree.
• The target node is identified by reference, not just by value.

Approach to Solve the Problem

To solve this problem, we can use one of the following approaches:

1. Recursive Traversal

Using recursion, we traverse both the original tree and the cloned tree simultaneously. At each step:

1. If the current node in the original tree matches the target node, return the corresponding node in the cloned tree.
2. Otherwise, recursively search the left and right subtrees.

2. Iterative Traversal

We can also solve this problem iteratively using a queue. The algorithm involves:

• Using two queues to perform a level-order traversal (BFS) on both trees simultaneously.
• At each step, compare the node from the original tree with the target node.
• If they match, return the corresponding node from the cloned tree.

3. Leveraging Tree Properties

Since the trees are identical in structure, we can use the symmetry of the cloned tree to locate the corresponding node directly during traversal. This avoids additional checks and comparisons.

Implementation

Here is the Java implementation for the recursive approach:

class Solution {
    public final TreeNode getTargetCopy(final TreeNode original, final TreeNode cloned, final TreeNode target) {
        // Base case: if the original node is null, return null
        if (original == null) {
            return null;
        }
        // If the current original node is the target, return the cloned node
        if (original == target) {
            return cloned;
        }
        // Recursively search in the left subtree
        TreeNode left = getTargetCopy(original.left, cloned.left, target);
        if (left != null) {
            return left;
        }
        // Recursively search in the right subtree
        return getTargetCopy(original.right, cloned.right, target);
    }
}
        

And here is the BFS-based iterative implementation:

class Solution {
    public final TreeNode getTargetCopy(final TreeNode original, final TreeNode cloned, final TreeNode target) {
        Queue queueOriginal = new LinkedList<>();
        Queue queueCloned = new LinkedList<>();
        queueOriginal.offer(original);
        queueCloned.offer(cloned);

        while (!queueOriginal.isEmpty()) {
            TreeNode currentOriginal = queueOriginal.poll();
            TreeNode currentCloned = queueCloned.poll();

            if (currentOriginal == target) {
                return currentCloned;
            }
            if (currentOriginal.left != null) {
                queueOriginal.offer(currentOriginal.left);
                queueCloned.offer(currentCloned.left);
            }
            if (currentOriginal.right != null) {
                queueOriginal.offer(currentOriginal.right);
                queueCloned.offer(currentCloned.right);
            }
        }
        return null;
    }
}
        

Complexity Analysis

Time Complexity: O(n), where n is the number of nodes in the binary tree. This is because we visit each node exactly once in both the original and cloned trees.

Space Complexity: O(h), where h is the height of the binary tree. This accounts for the stack space used in the recursive approach or the queue space in the iterative approach.

Example

Consider the following binary tree:

            Original Tree               Cloned Tree
                7                          7
               / \                        / \
              4   3                      4   3
                 / \                        / \
                6   19                     6   19
        

If the target node is 3 in the original tree, the corresponding node in the cloned tree is also 3.

Applications

• Useful in problems involving tree cloning and reference-based node identification.
• Demonstrates traversal techniques applicable to other tree-related problems.

Conclusion

This problem is a great exercise for understanding binary tree traversal and manipulation. The key takeaway is that, regardless of the approach (recursive or iterative), the identical structure of the cloned tree ensures that the corresponding node can always be located efficiently.

Explore this problem further by implementing it in different programming languages or extending it to handle more complex scenarios, such as multi-branch trees or trees with additional metadata.