Leetcode 1379: Find a Corresponding Node of a Binary Tree in a Clone of That Tree

Input: The input consists of two binary trees: the original tree and its clone, and a target node from the original tree.

Example: original_tree = [5,3,8,1,4,7,10], target = 4

Constraints:

• The number of nodes in the tree is between 1 and 10^4.

• The values of the nodes are unique.

• The target node is a node from the original tree and is not null.

Output: The output should be a reference to the corresponding node in the cloned tree.

Example: 4

Constraints:

• The node in the cloned tree that corresponds to the target node in the original tree should be returned.

Goal: The goal is to return a reference to the same node in the cloned tree as the target node in the original tree.

Steps:

• Traverse the cloned tree in parallel with the original tree.

• When the target node in the original tree is found, return the corresponding node from the cloned tree.

Goal: The problem needs to handle large trees efficiently.

Steps:

• The tree structure is valid and the values are unique in both the original and cloned trees.

Assumptions:

• The cloned tree is an exact copy of the original tree, including structure and values.

• Input: original_tree = [5,3,8,1,4,7,10], target = 4

• Explanation: The target node is `4` in the original tree, and its corresponding node in the cloned tree should be returned.

Approach: The problem can be solved by using a depth-first search (DFS) or breadth-first search (BFS) traversal to find the target node in the original tree and return the corresponding node from the cloned tree.

Observations:

• The original and cloned trees have the same structure and values.

• A depth-first search can be used to find the target node in the original tree, and the corresponding node in the cloned tree can be returned.

Steps:

• Start at the root of the original tree and cloned tree.

• Traverse both trees simultaneously using DFS.

• If the target node is found in the original tree, return the corresponding node from the cloned tree.

Empty Inputs:

• If there is only one node in the tree, return that node.

Large Inputs:

• Ensure the solution works for large trees with up to 10^4 nodes.

Special Values:

• If the target is the root of the tree, return the root from the cloned tree.

Constraints:

• The tree must have a valid structure with unique values.

TreeNode* ans;
TreeNode* getTargetCopy(TreeNode* original, TreeNode* cloned, TreeNode* target) 
{
    if (cloned == NULL)
        return cloned;
    if (cloned->val == target->val) // If target node found in cloned tree save it into a variable.
        ans = cloned;
    getTargetCopy(original, cloned->left, target);
    getTargetCopy(original, cloned->right, target);
    return ans;
}

1 : Variable Declaration

TreeNode* ans;

We declare a pointer `ans` of type `TreeNode*` that will hold the reference to the corresponding node in the cloned tree.

2 : Function Definition

TreeNode* getTargetCopy(TreeNode* original, TreeNode* cloned, TreeNode* target)

We define the function `getTargetCopy` that takes in three arguments: the original tree, the cloned tree, and the target node. It returns the corresponding node in the cloned tree.

3 : Base Case

    if (cloned == NULL)

We check if the current node in the cloned tree is `NULL`, which indicates we have reached a leaf or an empty subtree.

4 : Return Statement

        return cloned;

If the current node is `NULL`, we return `NULL` because there are no further nodes to check in this branch.

5 : Target Node Check

    if (cloned->val == target->val) // If target node found in cloned tree save it into a variable.

We check if the value of the current node in the cloned tree matches the target node's value.

6 : Assign Found Node

        ans = cloned;

If the values match, we assign the current node in the cloned tree to `ans` since it corresponds to the target node.

7 : Recursive Call (Left Subtree)

    getTargetCopy(original, cloned->left, target);

We make a recursive call to `getTargetCopy` to search the left subtree of the cloned tree.

8 : Recursive Call (Right Subtree)

    getTargetCopy(original, cloned->right, target);

We make a recursive call to `getTargetCopy` to search the right subtree of the cloned tree.

9 : Return Statement

    return ans;

Once both subtrees have been searched, we return the `ans` variable, which contains the reference to the corresponding node in the cloned tree.

Best Case: O(n)

Average Case: O(n)

Worst Case: O(n)

Description: The time complexity is O(n) where n is the number of nodes in the tree, since we need to traverse all nodes to find the target.

Best Case: O(1)

Worst Case: O(h)

Description: The space complexity is O(h) where h is the height of the tree, due to the recursion stack used during the DFS traversal.

Leetcode 1379: Find a Corresponding Node of a Binary Tree in a Clone of That Tree

Explore →