1379. Find Corresponding Node in Clone Tree

The problem

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?

Approach overview

Problem Overview: You are given two binary trees: the original tree and its exact clone. A reference to a target node exists in the original tree. Your task is to locate and return the corresponding node in the cloned tree. The trees have identical structure and values, but you must return the node from the cloned tree, not the original.

Approach 1: Recursive DFS (O(n) time, O(h) space)

This approach performs a synchronized depth-first traversal on both trees at the same time. Start at the roots of the original and cloned trees. If the current node in the original tree matches the target reference, return the corresponding node from the cloned tree. Otherwise, recursively search the left subtree, then the right subtree. Because both trees share the same structure, traversing them in parallel guarantees that when you reach the target node in the original tree, the corresponding node in the clone is at the same traversal position. Time complexity is O(n) since every node may be visited once. Space complexity is O(h) due to the recursion stack, where h is the tree height. This solution relies on concepts from Depth-First Search and Binary Tree traversal.

Approach 2: Iterative BFS (O(n) time, O(n) space)

The iterative solution uses a queue to perform a level-order traversal of both trees simultaneously. Push the root nodes of the original and cloned trees into the queue as a pair. Repeatedly dequeue a pair and check if the original node equals the target reference. If it does, return the cloned node from the pair. Otherwise, enqueue the left children and right children from both trees together. This keeps traversal aligned between the trees. The algorithm processes each node at most once, giving O(n) time complexity, while the queue may store up to a full level of nodes, resulting in O(n) space complexity. This approach demonstrates classic Breadth-First Search traversal.

Recommended for interviews: Recursive DFS is usually the expected solution because it is concise and clearly demonstrates understanding of tree traversal. Iterative BFS is equally correct and sometimes preferred when recursion depth might become large. Showing the DFS version first proves you understand how to traverse trees, while mentioning the BFS alternative shows breadth of problem-solving strategies.

Approach 1: Approach 1: Recursive DFS

This approach involves using a recursive depth-first search to simultaneously traverse both the original and cloned trees. When you find the target node in the original tree, return the corresponding node in the cloned tree.

Python

def getTargetCopy(original, cloned, target):
    if original is None:
        return None
    if original == target:
        return cloned
    left = getTargetCopy(original.left, cloned.left, target)
    if left:
        return left
    return getTargetCopy(original.right, cloned.right, target)

Java

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

C++

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

JavaScript

var getTargetCopy = function(original, cloned, target) {
    if (original === null) return null;
    if (original === target) return cloned;
    let left = getTargetCopy(original.left, cloned.left, target);
    if (left !== null) return left;
    return getTargetCopy(original.right, cloned.right, target);
};

TreeNode* getTargetCopy(TreeNode* original, TreeNode* cloned, TreeNode* target) {
    if (original == NULL) return NULL;
    if (original == target) return cloned;
    TreeNode* left = getTargetCopy(original->left, cloned->left, target);
    if (left != NULL) return left;
    return getTargetCopy(original->right, cloned->right, target);
}

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

The function getTargetCopy checks if the current node in the original tree is the target. If so, it returns the corresponding node in the cloned tree. Otherwise, it recursively searches the left subtree, then the right subtree.

Complexity

Time Complexity: O(N), where N is the number of nodes in the tree because each node is visited once.
Space Complexity: O(H), where H is the height of the tree due to the recursion stack.

Try this approach in the editor

Approach 2: Approach 2: Iterative BFS

Utilizing a queue, this approach explores both the original and cloned trees in parallel level-by-level. Once the target node is located in the original tree, the corresponding node in the cloned tree is returned.

Python

from collections import deque

def getTargetCopy(original, cloned, target):
    queue = deque([(original, cloned)])
    while queue:
        orig_node, clone_node = queue.popleft()
        if orig_node == target:
            return clone_node
        if orig_node.left:
            queue.append((orig_node.left, clone_node.left))
        if orig_node.right:
            queue.append((orig_node.right, clone_node.right))

Java

public TreeNode getTargetCopy(final TreeNode original, final TreeNode cloned, final TreeNode target) {
    Queue<TreeNode> queueOrig = new LinkedList<>();
    Queue<TreeNode> queueClone = new LinkedList<>();
    queueOrig.add(original);
    queueClone.add(cloned);
    while (!queueOrig.isEmpty()) {
        TreeNode nodeOrig = queueOrig.poll();
        TreeNode nodeClone = queueClone.poll();
        if (nodeOrig == target) {
            return nodeClone;
        }
        if (nodeOrig.left != null) {
            queueOrig.add(nodeOrig.left);
            queueClone.add(nodeClone.left);
        }
        if (nodeOrig.right != null) {
            queueOrig.add(nodeOrig.right);
            queueClone.add(nodeClone.right);
        }
    }
    return null;
}

C++

#include <queue>
using namespace std;

TreeNode* getTargetCopy(TreeNode* original, TreeNode* cloned, TreeNode* target) {
    queue<TreeNode*> queueOrig;
    queue<TreeNode*> queueClone;
    queueOrig.push(original);
    queueClone.push(cloned);
    while (!queueOrig.empty()) {
        TreeNode* nodeOrig = queueOrig.front(); queueOrig.pop();
        TreeNode* nodeClone = queueClone.front(); queueClone.pop();
        if (nodeOrig == target) return nodeClone;
        if (nodeOrig->left) {
            queueOrig.push(nodeOrig->left);
            queueClone.push(nodeClone->left);
        }
        if (nodeOrig->right) {
            queueOrig.push(nodeOrig->right);
            queueClone.push(nodeClone->right);
        }
    }
    return nullptr;
}

JavaScript

const getTargetCopy = function(original, cloned, target) {
    let queue = [[original, cloned]];
    while (queue.length > 0) {
        const [nodeOrig, nodeClone] = queue.shift();
        if (nodeOrig === target) return nodeClone;
        if (nodeOrig.left) queue.push([nodeOrig.left, nodeClone.left]);
        if (nodeOrig.right) queue.push([nodeOrig.right, nodeClone.right]);
    }
    return null;
};

TreeNode* getTargetCopy(TreeNode* original, TreeNode* cloned, TreeNode* target) {
    // Implementing a queue in C is cumbersome, usually done with linked lists or extensions in more robust environments.
    return NULL; // This represents a placeholder.
}

using System.Collections.Generic;

public TreeNode GetTargetCopy(TreeNode original, TreeNode cloned, TreeNode target) {
    Queue<TreeNode> queueOrig = new Queue<TreeNode>();
    Queue<TreeNode> queueClone = new Queue<TreeNode>();
    queueOrig.Enqueue(original);
    queueClone.Enqueue(cloned);
    while (queueOrig.Count > 0) {
        TreeNode nodeOrig = queueOrig.Dequeue();
        TreeNode nodeClone = queueClone.Dequeue();
        if (nodeOrig == target) return nodeClone;
        if (nodeOrig.left != null) {
            queueOrig.Enqueue(nodeOrig.left);
            queueClone.Enqueue(nodeClone.left);
        }
        if (nodeOrig.right != null) {
            queueOrig.Enqueue(nodeOrig.right);
            queueClone.Enqueue(nodeClone.right);
        }
    }
    return null;
}

This getTargetCopy function uses a queue to iteratively traverse the trees. It dequeues a pair of nodes, checks the original against the target, and enqueues children if necessary.

Complexity

Time Complexity: O(N)
Space Complexity: O(W), where W is the maximum width of the tree.

Try this approach in the editor

Approach 3: DFS

We design a function dfs(root1, root2), which performs DFS traversal simultaneously in trees root1 and root2. When traversing to a node, if this node happens to be target, then we return the corresponding node in root2. Otherwise, we recursively search for target in the left and right subtrees of root1 and root2, and return the result that is not empty.

The time complexity is O(n), and the space complexity is O(n). Where n is the number of nodes in the tree.

TypeScript

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

function getTargetCopy(
    original: TreeNode | null,
    cloned: TreeNode | null,
    target: TreeNode | null,
): TreeNode | null {
    const dfs = (root1: TreeNode | null, root2: TreeNode | null): TreeNode | null => {
        if (!root1) {
            return null;
        }
        if (root1 === target) {
            return root2;
        }
        return dfs(root1.left, root2.left) || dfs(root1.right, root2.right);
    };
    return dfs(original, cloned);
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Approach 1: Recursive DFS	Time Complexity: O(N), where N is the number of nodes in the tree because each node is visited once. Space Complexity: O(H), where H is the height of the tree due to the recursion stack.
Approach 2: Iterative BFS	Time Complexity: O(N) Space Complexity: O(W), where W is the maximum width of the tree.
DFS	–

Complexity analysis

Approach	Time	Space	When to Use
Recursive DFS	O(n)	O(h)	Preferred interview solution; clean recursive traversal with minimal extra memory
Iterative BFS	O(n)	O(n)	Useful when avoiding recursion or when using level-order traversal

Frequently asked questions

Is Find a Corresponding Node of a Binary Tree in a Clone of That Tree easy or hard?

This problem is classified as Easy on LeetCode with a high acceptance rate around 85 percent. The challenge mainly tests familiarity with binary tree traversal and understanding that the original and cloned trees share identical structure, allowing synchronized traversal to locate the corresponding node.

Find a Corresponding Node of a Binary Tree in a Clone of That Tree Python/Java solution

The Python and Java solutions typically implement either recursive DFS or iterative BFS. The DFS version checks if the current node equals the target and recursively searches left and right subtrees. Both implementations run in O(n) time and are concise because the original and cloned trees are traversed simultaneously.

How to solve Find a Corresponding Node of a Binary Tree in a Clone of That Tree in O(n)?

Traverse the original and cloned trees in parallel using DFS or BFS. Compare each visited node in the original tree with the target reference. When the target node is found, immediately return the corresponding node from the cloned tree. Because each node is processed once, the algorithm runs in O(n) time.

What is the best approach for Find a Corresponding Node of a Binary Tree in a Clone of That Tree?

The most common approach is a synchronized DFS traversal of both the original and cloned trees. Traverse both trees simultaneously and check whether the current node in the original tree matches the target reference. When a match is found, return the node from the cloned tree. This solution runs in O(n) time and O(h) space where h is the tree height.

Is Find a Corresponding Node of a Binary Tree in a Clone of That Tree asked at Google/Amazon/Meta?

Tree traversal problems like this frequently appear in technical interviews at large tech companies including Amazon, Google, and Meta. Interviewers often use variations involving binary tree traversal, cloning, or node mapping to test understanding of DFS, BFS, and pointer/reference handling.

What data structure is used in Find a Corresponding Node of a Binary Tree in a Clone of That Tree?

The primary data structure is a binary tree. The recursive solution uses the call stack to perform depth-first traversal, while the iterative solution uses a queue to perform breadth-first traversal. Both approaches rely on visiting nodes in the same structural order in both trees.

What is the time complexity of Find a Corresponding Node of a Binary Tree in a Clone of That Tree?

The time complexity is O(n) because every node in the binary tree may need to be visited once during traversal. Both DFS and BFS approaches scan the tree while maintaining alignment between the original and cloned trees. Space complexity is O(h) for recursive DFS due to the recursion stack or O(n) for BFS due to the queue.

Find a Corresponding Node of a Binary Tree in a Clone of That Tree solution and explanation

The problem

Approach overview

Approach 1: Approach 1: Recursive DFS

Approach 2: Approach 2: Iterative BFS

Approach 3: DFS

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Find a Corresponding Node of a Binary Tree in a Clone of That Tree solution and explanation

The problem

Approach overview

Approach 1: Approach 1: Recursive DFS

Approach 2: Approach 2: Iterative BFS

Approach 3: DFS

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems