We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

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

Number: 1498

Difficulty: Easy

Paid? No

Companies: Amazon, Meta

Problem Description

We are given two binary trees, original and cloned (where cloned is an exact copy of original), along with a target node in the original tree. The goal is to find and return the corresponding node in the cloned tree that occupies the same position as the target node in the original tree.

Key Insights

  • The cloned tree maintains the same structure as the original tree. Thus, the target node's position in the original tree directly corresponds to the same position in the cloned tree.
  • A synchronized traversal (using DFS or BFS) of both trees allows us to find the target node in the original and return the node at the corresponding position in the cloned tree.
  • The problem guarantees that the target node exists, so no further handling is needed for missing nodes.

Space and Time Complexity

Time Complexity: O(N) in the worst case, where N is the number of nodes, since we may traverse the entire tree in the worst-case scenario. Space Complexity: O(H) where H is the height of the tree, which is the space used by the recursion stack (or the queue if using BFS).

Solution

We perform a depth-first search (DFS) on both the original and cloned trees simultaneously. At each recursive call, we check if the current original node equals the target node. If it does, we return the corresponding cloned node. This synchronized traversal ensures that when we find the target in the original tree, the cloned tree's node at the same location is the answer.

Code Solutions

# 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':
        # If the current node in original equals the target, return the corresponding node in cloned.
        if original is target:
            return cloned
        # Check the left subtree.
        if original.left:
            left_result = self.getTargetCopy(original.left, cloned.left, target)
            if left_result:
                return left_result
        # Check the right subtree.
        if original.right:
            right_result = self.getTargetCopy(original.right, cloned.right, target)
            if right_result:
                return right_result
        # Return None if not found (the problem guarantees that the target exists).
        return None
← Back to All Questions