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

Easy

Asked by:

8 views

Topics:

TreesRecursion

Given two binary trees original and cloned and given a reference to a node target in the original tree.

The cloned tree is a copy of the original tree.

Return a reference to the same node in the cloned tree.

Note that you are not allowed to change any of the two trees or the target node and the answer must be a reference to a node in the cloned tree.

Example 1:

Input: tree = [7,4,3,null,null,6,19], target = 3
Output: 3
Explanation: 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 3:

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

Constraints:

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

Follow up: Could you solve the problem if repeated values on the tree are allowed?

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the binary tree contain duplicate node values, and if so, how should I handle them?
Is the target node guaranteed to be present in the original tree?
What should I return if the target node is null or if the original tree is empty?
What is the structure of the trees? Are they balanced or can they be skewed?
Are the tree node values unique within each tree, or can nodes have duplicate values?

Brute Force Solution

Approach

Imagine you have two identical family trees. We're trying to find a specific person in the second tree, knowing who they are in the first tree. The brute force approach is simply to check every single person in the second tree until we find the one that corresponds to the person we're looking for in the first tree.

Here's how the algorithm would work step-by-step:

Start at the very top of the clone tree (the root).
Check if this top person in the clone tree is the person we're looking for (the corresponding node). We check by comparing the path we took to get to this person from the root of the original tree.
If it's not the right person, move down one level and check the person to the left.
See if this person to the left is the corresponding person. If not, keep going down the left side of the clone tree, checking each person individually.
If we reach the end of the left side and still haven't found the person, go back up and check the other side (the right side) of the clone tree at each level, also checking each person individually.
Continue this process, checking every single person in the clone tree until we find the one that matches the path from the root of the original tree.

Code Implementation

def find_corresponding_node_brute_force(original_root, cloned_root, target_node):
    if not original_root or not cloned_root or not target_node:
        return None

    def path_to_node(root, target):
        if not root:
            return None
        if root == target:
            return []

        left_path = path_to_node(root.left, target)
        if left_path is not None:
            return ['L'] + left_path

        right_path = path_to_node(root.right, target)
        if right_path is not None:
            return ['R'] + right_path

        return None

    target_path = path_to_node(original_root, target_node)

    def find_node_by_path(root, path):
        if not root:
            return None

        current_node = root
        for direction in path:
            # Traverse the tree according to the path
            if direction == 'L':
                current_node = current_node.left
            else:
                current_node = current_node.right
            if not current_node:
                return None

        return current_node

    # Search for the corresponding node using the computed path
    corresponding_node = find_node_by_path(cloned_root, target_path)
    return corresponding_node

Big(O) Analysis

Time Complexity

O(n) – The algorithm, in the worst-case scenario, might have to traverse every node in the cloned tree to find the corresponding node. This traversal involves visiting each node once. Therefore, the number of operations is directly proportional to the number of nodes, n, in the tree. Thus, the time complexity is O(n).

Space Complexity

O(N) – The provided solution uses a brute-force approach involving a tree traversal of the clone tree. In the worst-case scenario, where the target node is the last node visited or doesn't exist, the algorithm may explore all N nodes of the clone tree through recursive calls. The recursion depth, which determines the number of stack frames used, can reach N in the worst case for a skewed tree. Therefore, the auxiliary space used by the call stack is proportional to N, resulting in a space complexity of O(N).

Optimal Solution

Approach

The key is to traverse both trees simultaneously. We explore both the original tree and its clone at the same time, step-by-step, until we find the target node in the original tree. The corresponding node in the cloned tree at that moment is our answer.

Here's how the algorithm would work step-by-step:

Begin by starting at the root of both the original tree and its cloned version.
Check if the current node in the original tree is the target node we are looking for.
If the current node in the original tree matches the target, then the current node in the cloned tree is the node we want, so we're done.
If we haven't found the target yet, we check if there are any child nodes.
If there are child nodes, move to the next set of corresponding child nodes in both trees and repeat the process.
Continue traversing the trees together until you find the target node in the original tree, and return the corresponding node from the cloned tree.

Code Implementation

def find_corresponding_node(
    original_tree, cloned_tree, target_node
):
    if not original_tree or not cloned_tree:
        return None

    queue_original = [original_tree]
    queue_cloned = [cloned_tree]

    while queue_original:
        current_original_node = queue_original.pop(0)
        current_cloned_node = queue_cloned.pop(0)

        # Check if the current original node is the target.
        if current_original_node == target_node:
            return current_cloned_node

        # Traverse to the next level
        if current_original_node.left:
            queue_original.append(current_original_node.left)
            queue_cloned.append(current_cloned_node.left)

        # Traverse to the next level
        if current_original_node.right:
            queue_original.append(current_original_node.right)
            queue_cloned.append(current_cloned_node.right)

    return None

Big(O) Analysis

Time Complexity

O(n) – The algorithm traverses both the original and cloned trees simultaneously. In the worst-case scenario, we might need to visit every node in the tree before finding the target node. Therefore, the time complexity is proportional to the number of nodes in the tree, represented as n. This corresponds to a single tree traversal, resulting in O(n) time complexity.

Space Complexity

O(H) – The space complexity is determined by the maximum depth of the recursion stack, where H is the height of the binary tree. In the worst-case scenario (a skewed tree), the recursion depth can be equal to the number of nodes, N. Therefore, the maximum auxiliary space used by the recursion stack is proportional to the height of the tree, or H. Thus the space complexity is O(H).

Edge Cases

Case	How to Handle
Both original and cloned trees are null	Return null immediately as there's no corresponding node.
Original tree is null, but cloned tree is not (or vice-versa)	Return null since there is no original to match.
Target node is the root node	The cloned tree's root should be returned directly if the target is original root.
Target node does not exist in the original tree	Return null if target node is not found during tree traversal.
Large trees with deep recursion stacks causing stack overflow	Consider an iterative approach (e.g., Breadth-First Search) to avoid stack overflow.
Trees with identical structures but different data (not the target node)	Ensure the comparison logic focuses on structure, not the data of other nodes.
Memory constraints with very large trees	Optimize the memory footprint of the search, possibly releasing memory used by visited nodes.
Cloned tree is not a true clone (structure is different)	The algorithm assumes a true clone, but if the structure differs, the corresponding node may not be found, returning null.

Both original and cloned trees are null

How to Handle:

Return null immediately as there's no corresponding node.

Original tree is null, but cloned tree is not (or vice-versa)

How to Handle:

Return null since there is no original to match.

Target node is the root node

How to Handle:

The cloned tree's root should be returned directly if the target is original root.

Target node does not exist in the original tree

How to Handle:

Return null if target node is not found during tree traversal.

Large trees with deep recursion stacks causing stack overflow

How to Handle:

Consider an iterative approach (e.g., Breadth-First Search) to avoid stack overflow.

Trees with identical structures but different data (not the target node)

How to Handle:

Ensure the comparison logic focuses on structure, not the data of other nodes.

Memory constraints with very large trees

How to Handle:

Optimize the memory footprint of the search, possibly releasing memory used by visited nodes.

Cloned tree is not a true clone (structure is different)

How to Handle:

The algorithm assumes a true clone, but if the structure differs, the corresponding node may not be found, returning null.