Vultr DocsLatest Content

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

Updated on 29 May, 2025
Find a Corresponding Node of a Binary Tree in a Clone of That Tree header image

Problem Statement

In this problem, you are given two binary trees: an original tree and its exact duplicate, the cloned tree. Additionally, you are provided with a reference to a node, target, which is part of the original tree. Your task is to find and return the corresponding node from the cloned tree which matches the target node from the original tree in terms of value and position but obviously, as a distinct object reference in the cloned tree. It is important to note that neither of the trees nor the target node can be modified during this process. Your solution must strictly identify and return a reference to the required node in the cloned tree without altering the structure or content of the trees.

Examples

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, 104].
  • The values of the nodes of the tree are unique.
  • target node is a node from the original tree and is not null.

Approach and Intuition

To solve the problem of finding the corresponding target node in the cloned tree, we can use a depth-first search (DFS) which is a common technique for tree traversal. Here's the intuitive breakdown of the steps:

  1. Start at the root of both the original and cloned trees.
  2. Traverse both trees simultaneously. Since the cloned is an exact copy of the original, they will have the same structure:
    • If the current node in the original tree is the target node, then the current node in the cloned tree is the answer.
    • Otherwise, proceed to recursively search in the left subtree if it exists.
    • If the target node is not found in the left subtree, proceed to recursively search the right subtree.
  3. Since binary tree nodes have unique values and the target node exists in the original tree (as per constraints), this method guarantees that the correct node will be found in the cloned tree.

This approach leverages the properties of the binary tree and the nature of the DFS to efficiently locate the corresponding node in the cloned version of the tree without modifying any elements, complying with the problem's constraints.

Solutions

  • Java
  • Python
java 
class Solution {
    public final TreeNode findTargetCopy(final TreeNode originalTree, final TreeNode clonedTree, final TreeNode targetNode) {
        Deque<TreeNode> queueOriginal = new ArrayDeque<>();
        queueOriginal.offer(originalTree);
        
        Deque<TreeNode> queueCloned = new ArrayDeque<>();
        queueCloned.offer(clonedTree);

        while (!queueOriginal.isEmpty()) {
            TreeNode currentOriginal = queueOriginal.poll();
            TreeNode currentCloned = queueCloned.poll();
            
            if (currentOriginal == targetNode) {
                return currentCloned;
            }
            
            if (currentOriginal.left != null) {
                queueOriginal.offer(currentOriginal.left);
                queueCloned.offer(currentCloned.left);
            }
            if (currentOriginal.right != null) {
                queueOriginal.offer(currentOriginal.right);
                queueCloned.offer(currentCloned.right);
            }
        }
        return null;
    }
}

This summary explains how to find a corresponding node in a cloned binary tree.

The provided Java function findTargetCopy takes three parameters: originalTree, clonedTree, and targetNode. The goal is to find the node in clonedTree that corresponds to targetNode in originalTree.

  • Start by initializing two Deque<TreeNode>: one for the original tree (queueOriginal) and one for the cloned tree (queueCloned).
  • Enqueue the root nodes of both the original and cloned trees into their respective queues.

Utilize a while loop that continues as long as there are nodes in the queueOriginal:

  • Dequeue the current nodes from both queues. If the current node from the original tree matches the targetNode, return the corresponding node from the cloned tree.
  • Enqueue the left child of the current node of the original tree to queueOriginal and the left child of the corresponding cloned node to queueCloned if they exist.
  • Repeat the previous step for the right children.

If the loop terminates without finding the targetNode, return null indicating the target node does not exist in the cloned tree.

This method ensures each node and its clone are compared in sync, which efficiently locates the corresponding node in the cloned tree.

python 
class Solution:
    def findTargetClone(self, orig: TreeNode, clone: TreeNode, targ: TreeNode) -> TreeNode:
        orig_queue = deque([orig])
        clone_queue = deque([clone])

        while orig_queue:
            orig_node = orig_queue.popleft()
            clone_node = clone_queue.popleft()
            
            if orig_node is targ:
                return clone_node

            if orig_node:
                orig_queue.append(orig_node.left)
                orig_queue.append(orig_node.right)
                
                clone_queue.append(clone_node.left)
                clone_queue.append(clone_node.right)

The code provided solves the problem of finding the corresponding node in a cloned binary tree based on a target node in the original tree. It uses a breadth-first search approach with two queues to simultaneously traverse both the original and cloned trees. As it traverses, the code checks each node from the original tree against the target node. When the target node is found, it immediately returns the corresponding node from the cloned tree.

Here's how the solution operates:

  1. Initialize two double-ended queues (deque), one for the original tree and one for the cloned tree.
  2. Start by enqueuing the root nodes of both trees.
  3. Use a while loop to traverse the trees as long as there are nodes in the original tree's queue.
    • Dequeue the front node from both the original and cloned tree queues.
    • Check if the dequeued node from the original tree is the target node. If so, return the corresponding node from the clone queue.
    • If the node has children, enqueue the left and right children into the respective queues.

This method ensures that both trees are traversed in a synchronized manner, keeping the nodes at equivalent positions in the queue, which allows for matching the nodes from the original tree to the cloned tree correctly.

Comments

No comments yet.