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

Find a Corresponding Node of a Binary Tree in a Clone of That Tree - 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
The answer must be a reference to a node in the cloned tree

Input & Output

Example 1 — Basic Tree

$ Input: original = [7,4,3,null,null,6,19], cloned = [7,4,3,null,null,6,19], target = 3

› Output: 3

💡 Note: The target node has value 3. We find the corresponding node in the cloned tree and return it.

Example 2 — Single Node

$ Input: original = [7], cloned = [7], target = 7

› Output: 7

💡 Note: Both trees have only one node. The target is the root, so we return the cloned root.

Example 3 — Duplicate Values

$ Input: original = [8,null,6,null,5,null,4,null,3,null,2,null,1], cloned = [8,null,6,null,5,null,4,null,3,null,2,null,1], target = 4

› Output: 4

💡 Note: Even with duplicate values possible, we find the exact corresponding node position in the cloned tree.

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

Visualization

Tap to expand

Understanding the Visualization

Input

Two identical trees and target node from original

Process

Traverse both trees simultaneously to find corresponding position

Output

Return reference to corresponding node in cloned tree

Key Takeaway

🎯 Key Insight: Since trees are identical, traverse both simultaneously and return cloned node when target is found in original

Asked in

F Facebook 15 A Amazon 12 G Google 8

The key insight is to traverse both original and cloned trees simultaneously using DFS. When we find the target node in the original tree, we return the corresponding node from the cloned tree at the same position. Best approach is Simultaneous DFS with Time: O(n), Space: O(h).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Find by Value	O(n)	O(h)	Search cloned tree for node with same value as target
Simultaneous DFS Traversal	O(n)	O(h)	Traverse both trees simultaneously to find corresponding position

Brute Force - Find by Value — Algorithm Steps

Step 1: Get target node's value
Step 2: Traverse cloned tree using DFS
Step 3: Return first node with matching value

Visualization

Tap to expand

Step-by-Step Walkthrough

Identify Target

Get target node's value from original tree

DFS Search

Traverse cloned tree looking for matching value

Return Match

Return first node with same value

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct TreeNode {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
};

struct TreeNode* createNode(int val) {
    struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    node->val = val;
    node->left = NULL;
    node->right = NULL;
    return node;
}

struct TreeNode* dfs(struct TreeNode* node, int targetVal) {
    if (!node) return NULL;
    if (node->val == targetVal) return node;
    struct TreeNode* left = dfs(node->left, targetVal);
    if (left) return left;
    return dfs(node->right, targetVal);
}

struct TreeNode* solution(struct TreeNode* original, struct TreeNode* cloned, struct TreeNode* target) {
    return dfs(cloned, target->val);
}

int main() {
    // Simplified for demo - assume single node trees
    struct TreeNode* original = createNode(7);
    struct TreeNode* cloned = createNode(7);
    struct TreeNode* target = original;
    
    struct TreeNode* result = solution(original, cloned, target);
    if (result) {
        printf("%d\n", result->val);
    } else {
        printf("null\n");
    }
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Visit all nodes in cloned tree in worst case

✓ Linear Growth

Space Complexity

O(h)

Recursion stack depth equals tree height h

✓ Linear Space

89.7K Views

Medium Frequency

~10 min Avg. Time

1.5K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Find by Value — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler