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

leetcode.com/problems/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.

Follow up: Solve the problem if repeated values on the tree are allowed.

Example 1:

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:

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

Example 3:

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

Example 4:

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

Example 5:

Input: tree = [1,2,null,3], target = 2 Output: 2

Constraints:

The number of nodes in the tree is in the range [1, 10^4].
The values of the nodes of the tree are unique.
target node is a node from the original tree and is not null.

Solution

Overview

How to Solve

Let's traverse both trees in parallel, and once the target node is identified in the first tree, return the corresponding node from the second tree.

How to Traverse the Tree: DFS vs BFS

There are two ways to traverse the tree: DFS depth first search and BFS breadth first search. Here is a small summary

Both are starting from the root and going down, both are using additional structures, what's the difference? Here is how it looks at the big scale: BFS traverses level by level, and DFS first goes to the leaves.

Description doesn't give us any clue which traversal is better to use here. Interview-simple solutions are DFS inorder traversals.

In the Approach 1 and Approach 2 we're going to discuss recursive inorder DFS and iterative inorder DFS traversals. They both need up to \mathcal{O}(H) space to keep stack, where H is a tree height.

In the Approach 3, we provide a BFS solution. Normally, it's a bad idea to use BFS during the interview, unless the interviewer would push for it by adding new details into the problem description.

Could We Solve in Constant Space?

No. The problem could be solved in constant space using DFS Morris inorder traversal algorithm, but it modifies the tree, and that isn't allowed here.

Follow up: Repeated Values are Allowed

If duplicate values are not allowed, one could compare node values:

Otherwise, one has to compare the nodes:

Approach 1: DFS: Recursive Inorder Traversal.

Recursive inorder traversal is extremely simple: follow Left->Node->Right direction, i.e., do the recursive call for the left child, then do all the business with the node (= check if the node is a target one or not), and then do the recursive call for the right child.

Figure 1. The nodes are enumerated in the order of visit. To compare different DFS strategies, follow 1-2-3-4-5 direction.

Implementation

class Solution:
    def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:
        
        def inorder(o: TreeNode, c: TreeNode):
            if o:
                inorder(o.left, c.left)
                if o is target:
                    self.ans = c
                inorder(o.right, c.right)
        inorder(original, cloned)
        return self.ans

Complexity Analysis

Time complexity: \mathcal{O}(N) since one has to visit each node, where N is a number of nodes.
Space complexity: up to \mathcal{O}(H) to keep the recursion stack, where H is a tree height.

Approach 2: DFS: Iterative Inorder Traversal.

Iterative inorder traversal is straightforward: go left as far as you can, then one step right. Repeat till the end of nodes in the tree.

1 / 9

Implementation

Don't use Stack in Java, use ArrayDeque instead.

class Solution:
    def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:
        stack_o, stack_c = [], []
        node_o, node_c = original, cloned
        
        while stack_o or node_c:
            while node_o:
                stack_o.append(node_o)
                stack_c.append(node_c)
                
                node_o = node_o.left
                node_c = node_c.left
            
            node_o = stack_o.pop()
            node_c = stack_c.pop()
            
            if node_o is target:
                return node_c
            
            node_o = node_o.right
            node_c = node_c.right

Complexity Analysis

Time complexity: \mathcal{O}(N) since one has to visit each node.
Space complexity: up to \mathcal{O}(H) to keep the stack, where H is a tree height.

Approach 3: BFS: Iterative Traversal.

Algorithm

Here we implement standard BFS traversal with the queue:

Add root into queue.
While queue is not empty:
- Pop out a node from queue.
- If the node is a target, we're done.
- Add first left and then right child node into queue.

Implementation

Don't use Stack in Java, use ArrayDeque instead.

class Solution:
    def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:
        queue_o = deque([original, ])
        queue_c = deque([cloned, ])
        
        while queue_o:
            node_o = queue_o.popleft()
            node_c = queue_c.popleft()
            
            if node_o is target:
                return node_c
            
            if node_o:
                queue_o.append(node_o.left)
                queue_o.append(node_o.right)
                
                queue_c.append(node_c.left)
                queue_c.append(node_c.right)

Complexity Analysis

Time complexity: \mathcal{O}(N) since one has to visit each node.
Space complexity: up to \mathcal{O}(N) to keep the queue. Let's use the last level to estimate the queue size. This level could contain up to N/2 tree nodes in the case of complete binary tree.