algoadvance

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

Problem Statement

Given two binary trees original and cloned and given a reference to a node target in the original tree, you need to find the corresponding node in the cloned tree.

Clarifying Questions

1. Are the original and cloned trees structurally identical?
   • Yes, the trees will be identical in structure.
2. Can the values of the nodes in the trees be duplicated?
   • Yes, nodes can have the same values, so do not rely on the values to find the target.
3. Will the target node always exist in the original tree?
   • Yes, the target node will always be present in the original tree.

Strategy

1. Understanding Trees Identity: The cloned tree is an exact copy of the original tree, but they are separate objects.
2. Tree Traversal: Use a traversal (DFS or BFS) to find the node in the cloned tree that corresponds to the target node from the original tree.
3. Node Reference: Instead of using values to find the target, use the node reference directly.
4. Depth-First Search (DFS): Apply DFS recursively or iteratively to simultaneously traverse both the original and cloned trees. When we find the target node in the original tree, we return the corresponding node in the cloned tree.

Code

Here’s a possible implementation:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */

public class Solution {
    public final TreeNode getTargetCopy(final TreeNode original, final TreeNode cloned, final TreeNode target) {
        if (original == null) {
            return null;
        }

        if (original == target) {
            return cloned;
        }

        TreeNode leftResult = getTargetCopy(original.left, cloned.left, target);
        if (leftResult != null) {
            return leftResult;
        }
        
        return getTargetCopy(original.right, cloned.right, target);
    }
}

Explanation

1. Base Case: If the original node is null, return null. This means we’ve reached the end of a branch without finding the target.
2. Check Target: If the current node in the original tree is the target node, return the corresponding node in the cloned tree.
3. Traverse Left: Recursively check the left subtree.
4. Traverse Right: If the left subtree did not yield the target, recursively check the right subtree.

Time Complexity

• Time Complexity: (O(N)), where (N) is the number of nodes in the tree. In the worst case, we might need to traverse all nodes.
• Space Complexity: (O(H)), where (H) is the height of the tree due to the recursion stack. In the worst case (unbalanced tree), it could be (O(N)).

This approach ensures that we efficiently find the corresponding node in the cloned tree without relying on the values of the nodes.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?