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

Problem Link: https://leetcode.com/problems/find-a-corresponding-node-of-a-binary-tree-in-a-clone-of-that-tree/

Photo by Arnaud Mesureur on Unsplash

Problem Description: 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.
Follow up: Solve the problem if repeated values on the tree are allowed.

Approach Used: Tree traversal, Stack

Explanation: I used two methods. First to store the path we followed in the original tree to reach the target node. This is done by recursively searching the left and right tree and if a match is found. Then we start storing the path. To store the path we make a note that whether the node was found in the left tree of the current node or right tree of the current node or current node is the target node. I did this by making a character stack storing ‘l’, ‘r’, ‘c’ corresponding to the three cases. Since we start storing the path after reaching the target, we use a stack to store it.
Then we send the same path stack for traversal in the cloned tree and reach the target node in the cloned tree.
For handling case with duplicate node value, we compare the addresses of the node instead of the value.

Best Approach: The approach I used is clearly not the best one. You can directly do inorder traversal on both trees simultaneously and compare the target node with the original tree’s nodes and if it matches, we return the corresponding node of the cloned tree.

Code: (Java)

//first method to store the path bby traversing the original tree
    public static Stack<Character> getPath(TreeNode original, TreeNode target){
        //base case - if tree null at any recursion then target cannot be found so no path
        if(original==null)
            return null;
        
        //if target found, then create a stack and store 'c' to represent this is target node
        if(original==target){
            Stack<Character> ans = new Stack<Character>();
            ans.push('c');
            return ans;
        }
        
        //if not target node
        //search left tree 
        Stack<Character> left = getPath(original.left, target);
        //if left stack is null then target node not in left sub tree
        if(left!=null){
            //if not null then taget in left sub tree of current node, so push 'l'
            left.push('l');
            //return the path to parent node
            return left;
        }
        //only checked if node not in left sub tree
        //if right stack is null then target node not in right sub tree
        Stack<Character> right = getPath(original.right, target);
        if(right!=null){
            //push r for second case
            right.push('r');
            return right;
        }
        
        //if node not in both left and right subtree then return no path to parent
        return null;
    }
    public final TreeNode traversePath(TreeNode node, Stack<Character> path){
        //handle all base cases
        if(node==null || path.size()<=0 || path==null || path.peek()=='c')
            return node;
        //find direction for next recursion
        Character c = path.pop();
        
        //case 1
        if(c=='l'){
            return traversePath(node.left, path);
        }
        //case 2
        else if(c=='r'){
            return traversePath(node.right, path);
        }
        
        return node;
    }
    public final TreeNode getTargetCopy(final TreeNode original, final TreeNode cloned, final TreeNode target) {
        //get path in original array
        Stack<Character> path = getPath(original, target);
        //traverse path in cloned array
        return traversePath(cloned, path);
    }

Complexity:
Space Complexity: O(h). Since we are doing a DFS, maximum nodes that can be stored at any point is equal to the maximum height of the tree.
Time Complexity: O(n). in the worst case we might visit all the nodes once.