#1379

Easy

auto_awesomeBinary-tree traversal and state tracking

LeetCode Problem Workspace

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

Find the corresponding node in a cloned binary tree using binary-tree traversal and state tracking.

tree depth first search breadth first search binary tree

Problem Statement

You are given two binary trees: an original tree and its cloned version. A reference to a target node in the original tree is also provided. Your task is to return the corresponding node in the cloned tree that matches the target node from the original tree.

The trees are identical in structure, with the same node values, and the target node exists in the original tree. The challenge is to efficiently find the corresponding node in the cloned tree, using binary-tree traversal techniques and state tracking to match the original and cloned trees correctly.

Examples

Example 1

Input: tree = [7,4,3,null,null,6,19], target = 3

Output: 3

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 details omitted.

Example 3

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

Output: 4

Example details omitted.

Constraints

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

Solution Approach

Binary-Tree Traversal

You can use Depth-First Search (DFS) or Breadth-First Search (BFS) to traverse both trees simultaneously. As you traverse, compare the nodes from the original and cloned trees. Once you find the node in the original tree that matches the target, return the corresponding node in the cloned tree.

State Tracking

While traversing, maintain state to track the correspondence between the original and cloned trees. Since both trees have identical structures and node values, the node in the cloned tree corresponding to the target node in the original tree will be found when both traversal processes align on the same node.

Optimized Traversal

Given that both DFS and BFS offer linear time complexity, the solution can be optimized by using either method to efficiently search through the trees. The problem has a linear time complexity of O(N), where N is the number of nodes in the tree, which ensures an efficient solution even with large trees.

Complexity Analysis

Metric	Value
Time	\mathcal{O}(N)
Space	up to

The time complexity is O(N) because we need to traverse all nodes in the binary tree to find the target node. The space complexity can be up to O(N) if the traversal requires storing nodes in memory (for example, in DFS or BFS queues).

What Interviewers Usually Probe

Tests the candidate's understanding of binary tree traversal techniques.
Assesses the ability to maintain state during traversal.
Tests problem-solving skills in efficiently matching nodes between original and cloned trees.

Common Pitfalls or Variants

Common pitfalls

Confusing the target node in the original tree with its corresponding node in the cloned tree.
Using an inefficient traversal that leads to unnecessary computations.
Failing to track the state correctly between the two trees during traversal.

Follow-up variants

Different traversal methods: DFS vs BFS for the tree search.
Handling trees of varying sizes and depths.
Finding corresponding nodes in a non-binary tree (extension to n-ary trees).

FAQ

What is the best traversal method to solve the problem 'Find a Corresponding Node of a Binary Tree in a Clone of That Tree'?

Both DFS and BFS are effective for this problem. The choice depends on your preference and the tree structure, but both have a time complexity of O(N).

Can I solve this problem in less than O(N) time?

No, because you need to examine each node at least once in the worst case. Thus, O(N) is the optimal time complexity for this problem.

How do I track the state between the original and cloned trees during traversal?

You can track the state by ensuring that for every node visited in the original tree, the corresponding node is visited in the cloned tree. This can be done by following the same traversal path in both trees.

What are the constraints of the 'Find a Corresponding Node of a Binary Tree in a Clone of That Tree' problem?

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

What should I do if the binary trees are not perfectly balanced?

The solution approach works regardless of whether the trees are balanced or not. Both DFS and BFS will traverse all nodes in the tree without any assumptions about balance.

terminal

Solution

Solution 1: DFS

We design a function $dfs(root1, root2)$, which performs DFS traversal simultaneously in trees $root1$ and $root2$. When traversing to a node, if this node happens to be $target$, then we return the corresponding node in $root2$. Otherwise, we recursively search for $target$ in the left and right subtrees of $root1$ and $root2$, and return the result that is not empty.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None


class Solution:
    def getTargetCopy(
        self, original: TreeNode, cloned: TreeNode, target: TreeNode
    ) -> TreeNode:
        def dfs(root1: TreeNode, root2: TreeNode) -> TreeNode:
            if root1 is None:
                return None
            if root1 == target:
                return root2
            return dfs(root1.left, root2.left) or dfs(root1.right, root2.right)

        return dfs(original, cloned)

Continue Practicing

#1361 validate binary tree nodes #1315 sum of nodes with even valued grandparent #1448 count good nodes in binary tree