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

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

✓ Sliding Window

⏱️ Time: N/A Space: N/A

Optimized

⏱️ Time: N/A Space: N/A

Brute Force - Find by Value

⏱️ Time: O(n) Space: O(h)

Traverse the entire cloned tree and return the first node that has the same value as the target node. This assumes all node values are unique.

Simultaneous DFS Traversal

⏱️ Time: O(n) Space: O(h)

Walk through both original and cloned trees at the same time using depth-first search. When we reach the target node in the original tree, we return the corresponding node in the cloned tree.

Algorithm Steps — Algorithm Steps

Code -

solution.c — C

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

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

typedef struct QueueNode {
    TreeNode* tree_node;
    struct QueueNode* next;
} QueueNode;

typedef struct Queue {
    QueueNode* front;
    QueueNode* rear;
} Queue;

Queue* createQueue() {
    Queue* q = (Queue*)malloc(sizeof(Queue));
    q->front = q->rear = NULL;
    return q;
}

void enqueue(Queue* q, TreeNode* node) {
    QueueNode* temp = (QueueNode*)malloc(sizeof(QueueNode));
    temp->tree_node = node;
    temp->next = NULL;
    if (q->rear == NULL) {
        q->front = q->rear = temp;
        return;
    }
    q->rear->next = temp;
    q->rear = temp;
}

TreeNode* dequeue(Queue* q) {
    if (q->front == NULL) return NULL;
    QueueNode* temp = q->front;
    TreeNode* result = temp->tree_node;
    q->front = q->front->next;
    if (q->front == NULL) q->rear = NULL;
    free(temp);
    return result;
}

bool isEmpty(Queue* q) {
    return q->front == NULL;
}

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

int parseArray(const char* str, char values[][10], int maxSize) {
    int count = 0;
    const char* p = str;
    
    while (*p && *p != '[') p++;
    if (*p == '[') p++;
    
    while (*p && *p != ']' && count < maxSize) {
        while (*p == ' ' || *p == ',') p++;
        if (*p == ']' || *p == '\0') break;
        
        int i = 0;
        if (strncmp(p, "null", 4) == 0) {
            strcpy(values[count], "null");
            p += 4;
        } else {
            while (*p && *p != ',' && *p != ']' && *p != ' ') {
                values[count][i++] = *p++;
            }
            values[count][i] = '\0';
        }
        count++;
    }
    
    return count;
}

TreeNode* buildTree(char values[][10], int size) {
    if (size == 0 || strcmp(values[0], "null") == 0) {
        return NULL;
    }
    
    TreeNode* root = createNode(atoi(values[0]));
    Queue* q = createQueue();
    enqueue(q, root);
    int i = 1;
    
    while (!isEmpty(q) && i < size) {
        TreeNode* node = dequeue(q);
        
        if (i < size && strcmp(values[i], "null") != 0) {
            node->left = createNode(atoi(values[i]));
            enqueue(q, node->left);
        }
        i++;
        
        if (i < size && strcmp(values[i], "null") != 0) {
            node->right = createNode(atoi(values[i]));
            enqueue(q, node->right);
        }
        i++;
    }
    
    return root;
}

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

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

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

int main() {
    char line1[10000];
    char line2[10000];
    char line3[100];
    
    fgets(line1, sizeof(line1), stdin);
    fgets(line2, sizeof(line2), stdin);
    fgets(line3, sizeof(line3), stdin);
    
    char originalValues[1000][10];
    char clonedValues[1000][10];
    
    int originalSize = parseArray(line1, originalValues, 1000);
    int clonedSize = parseArray(line2, clonedValues, 1000);
    int targetVal = atoi(line3);
    
    TreeNode* original = buildTree(originalValues, originalSize);
    TreeNode* cloned = buildTree(clonedValues, clonedSize);
    TreeNode* target = findTargetNode(original, targetVal);
    
    TreeNode* resultNode = solution(original, cloned, target);
    printf("%d\n", resultNode ? resultNode->val : 0);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

✓ Linear Growth

Space Complexity

✓ 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