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

Problem: You are given two binary trees original and cloned. As the names suggested the cloned tree is a copy of the original tree. Given a reference to a node target in the original tree, return a reference to the same node in the cloned tree.

Example:

Input: trees are given in the image, target = 3
Output: 3
Explanation: In the example the original and cloned trees are shown. The target node is pointed by yellow arrow from the original tree. The answer is the node pointed by red arrow from the cloned tree.

Approach: The approach is simple, apply any traversal to both the trees. While traversing whenever we find the current node in the original tree is same as target node, we return the current node of the cloned tree. Please note that compare the nodes, do not compare the values as tree can have duplicate value. I am using pre-order traversal here.

Implementation in C#:

        public BinaryTreeNode GetTargetCopy(BinaryTree clonedTree, BinaryTreeNode target)

        {

            if (target == null || this.Root == null || clonedTree.Root == null)

            {

                return null;

            }

            return this.GetTargetCopy(this.Root, clonedTree.Root, target);

        }

        private BinaryTreeNode GetTargetCopy(BinaryTreeNode original, BinaryTreeNode cloned, BinaryTreeNode target)

        {

            if (original == null)

            {

                return null;

            }

            if (original == target)

            {

                return cloned;

            }

            BinaryTreeNode targetNode = this.GetTargetCopy(original.LeftNode, cloned.LeftNode, target);

            if (targetNode != null)

            {

                return targetNode;

            }

            return this.GetTargetCopy(original.RightNode, cloned.RightNode, target);

        }

Complexity: O(n)