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 a reference to a node target in the original tree, you need to find the node in the cloned tree that corresponds to the target node in the original tree.

Both trees are identical versions of each other, and cloned is a copy of the original tree.

Clarifying Questions

  1. Is the structure of the cloned tree guaranteed to be exactly the same as the original tree?
    • Yes, the structure and values are identical.
  2. Can the target node be any node within the original tree?
    • Yes, the target node can be any node within the tree.
  3. Can target node be nullptr?
    • No, the target node will always be a valid node within the tree.
  4. Are there any constraints on the size of the tree?
    • Typical constraints for a binary tree in LeetCode problems, usually up to a few thousand nodes.

Strategy

We will perform a Depth-First Search (DFS) on both trees simultaneously. While traversing both trees together, we will check if the node in the original tree matches the target node. When we find the node in the original tree that matches the target, we return the corresponding node in the cloned tree.

Steps:

  1. Utilize a DFS traversal starting from the root nodes of both trees simultaneously.
  2. At each step, check if the current node in the original tree is the target node.
  3. If it is, return the corresponding node in the cloned tree.
  4. If not, traverse the left and right subtrees.

Code

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */

class Solution {
public:
    TreeNode* getTargetCopy(TreeNode* original, TreeNode* cloned, TreeNode* target) {
        if (original == nullptr) return nullptr;
        
        if (original == target) return cloned;
        
        TreeNode* leftResult = getTargetCopy(original->left, cloned->left, target);
        if (leftResult != nullptr) return leftResult;
        
        return getTargetCopy(original->right, cloned->right, target);
    }
};

Time Complexity

The time complexity of this algorithm is (O(N)), where (N) is the number of nodes in the tree. This is because we may potentially need to visit all nodes in the tree to find the target node.

The space complexity of the algorithm is (O(H)), where (H) is the height of the tree, considering the auxiliary stack space used by the recursion. In the worst case, for a completely unbalanced tree, (H) can be (N). For a balanced tree, (H) will be (O(\log N)).

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