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

You can solve this problem by performing a depth-first search (DFS) on both trees simultaneously.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:
    def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:
        # Create a stack for original tree and cloned tree
        stack_original = [original]
        stack_cloned = [cloned]

        # Perform Depth-First Search on both trees
        while stack_original:
            node_original = stack_original.pop()
            node_cloned = stack_cloned.pop()

            # If the current node in the original tree is the target, return the corresponding node in the cloned tree
            if node_original is target:
                return node_cloned

            # If the node in the original tree has a left child, add it to the stack, along with its counterpart in the cloned tree
            if node_original.left:
                stack_original.append(node_original.left)
                stack_cloned.append(node_cloned.left)

            # If the node in the original tree has a right child, add it to the stack, along with its counterpart in the cloned tree
            if node_original.right:
                stack_original.append(node_original.right)
                stack_cloned.append(node_cloned.right)

In the code, we depth-first search (DFS) on the original tree and the cloned tree at the same time. When we find the target node in the original tree, we return the corresponding node in the cloned tree. As we’re exploring the trees in the same order, the nodes we’re examining in the cloned tree will always correspond to the nodes we’re examining in the original tree.