# Find a Corresponding Node of a Binary Tree in a Clone of That Tree
**Difficulty:** EASY
[External](https://leetcode.com/problems/find-a-corresponding-node-of-a-binary-tree-in-a-clone-of-that-tree)
Canonical: https://scaleengineer.com/dsa/problems/find-a-corresponding-node-of-a-binary-tree-in-a-clone-of-that-tree
**Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search), [Breadth-First Search](https://scaleengineer.com/algorithms/breadth-first-search)
**Data structures:** Tree, Binary 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 and the answer **must be** a reference to a node in the `cloned` tree.

**Example 1:**

![](https://assets.glich.co/dsa/find-a-corresponding-node-of-a-binary-tree-in-a-clone-of-that-tree/image0.png) 

**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:**

![](https://assets.glich.co/dsa/find-a-corresponding-node-of-a-binary-tree-in-a-clone-of-that-tree/image1.png) 

**Input:** tree = [7], target =  7
**Output:** 7

**Example 3:**

![](https://assets.glich.co/dsa/find-a-corresponding-node-of-a-binary-tree-in-a-clone-of-that-tree/image2.png) 

**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`.

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

# Approaches
## Traversal by Value
This approach first finds the value of the `target` node in the `original` tree. Then, it performs a standard tree traversal (like pre-order, in-order, or BFS) on the `cloned` tree to find the node with the same value. This works only because the problem statement guarantees that all node values are unique.
**Time:** O(N), where N is the number of nodes in the tree. In the worst case, the target node might be the last one visited in the traversal of the `cloned` tree. · **Space:** O(H), where H is the height of the tree. This space is used by the recursion stack. In the worst case of a skewed tree, H can be N, making the space complexity O(N). For a balanced tree, it's O(log N).
**Pros:** Conceptually simple and easy to implement.
**Cons:** This approach will fail if the tree contains duplicate node values, as it might return the wrong node. It is not a general solution and only works because of the specific constraint that values are unique.
### Explanation
The core idea is to use the `target` node's value as a unique identifier. Since the problem statement guarantees that all node values in the tree are unique, finding a node with the same value in the `cloned` tree is sufficient to locate the corresponding node.

The algorithm proceeds in two conceptual steps:
1.  Retrieve the value of the target node: `int targetValue = target.val;`
2.  Traverse the `cloned` tree. A recursive pre-order traversal is a straightforward way to implement this.
3.  In the traversal function, for each visited node in the `cloned` tree, compare its value with `targetValue`.
4.  If a match is found, that node is the answer, and we can return it, terminating the search.

```java
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */

class Solution {
    public final TreeNode getTargetCopy(final TreeNode original, final TreeNode cloned, final TreeNode target) {
        if (original == null) {
            return null;
        }
        // Use a helper function to search in the cloned tree by value
        return findNodeByValue(cloned, target.val);
    }

    private TreeNode findNodeByValue(TreeNode node, int value) {
        if (node == null) {
            return null;
        }
        if (node.val == value) {
            return node;
        }
        TreeNode leftResult = findNodeByValue(node.left, value);
        if (leftResult != null) {
            return leftResult;
        }
        return findNodeByValue(node.right, value);
    }
}
```
### Algorithm
*   Get the value of the `target` node, let's call it `val`.
*   Start a traversal on the `cloned` tree from its root. A recursive pre-order traversal is a common choice.
*   For each node visited in the `cloned` tree:
    *   Check if the node's value is equal to `val`.
    *   If it is, return this node.
*   If the traversal completes without finding the node, return `null` (though this won't happen based on problem constraints).

## Simultaneous Traversal of Both Trees
This is a more robust approach that traverses both the `original` and `cloned` trees at the same time, in the same order (e.g., pre-order). By moving in lockstep through both trees, when we encounter the `target` node in the `original` tree, the current node in the `cloned` tree traversal is guaranteed to be its corresponding copy. This method works even if the tree contains duplicate values.
**Time:** O(N), where N is the number of nodes. We visit each node at most once. On average, if the target is randomly located, we'd visit N/2 nodes. The worst case is visiting N nodes if the target is the last node in the traversal order. · **Space:** O(H), where H is the height of the tree. This space is for the recursion stack. In the worst case of a skewed tree, this is O(N). For a balanced tree, it's O(log N).
**Pros:** Correctly solves the problem even if node values are not unique, making it a robust and general solution.; It is efficient as it stops the traversal as soon as the target is found.; It directly addresses the problem by tracking the path to the target node structurally, rather than relying on potentially non-unique data.
**Cons:** The recursive implementation might lead to a stack overflow for very deep (skewed) trees, though this is unlikely given the constraint of 10^4 nodes. An iterative version using a stack can avoid this potential issue.
### Explanation
This method does not rely on node values, but on the identical structure of the two trees and the reference to the `target` node itself. We can use any standard traversal method (DFS like pre-order, in-order, post-order, or BFS) as long as we apply it to both trees simultaneously.

Let's use a recursive pre-order traversal. The recursive function will take the current node from the `original` tree and the current node from the `cloned` tree as arguments.

The base case for the recursion is when the current original node is `null`.

The main check inside the function is `if (original_node == target)`. If this condition is true, we have found the node we are looking for in the original tree, so we can immediately return its counterpart, `cloned_node`.

If the current node is not the target, we continue the search by making recursive calls on the left children (`original_node.left`, `cloned_node.left`) and then the right children (`original_node.right`, `cloned_node.right`). The search is optimized to stop as soon as the target is found in either subtree.

```java
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */

class Solution {
    public final TreeNode getTargetCopy(final TreeNode original, final TreeNode cloned, final TreeNode target) {
        // Base case: if the current original node is null, we've reached the end of a path.
        if (original == null) {
            return null;
        }

        // Check if the current original node is the target node.
        // We compare by reference, not by value.
        if (original == target) {
            return cloned;
        }

        // Recursively search in the left subtree.
        TreeNode leftResult = getTargetCopy(original.left, cloned.left, target);
        // If the target was found in the left subtree, the result will not be null.
        // We can return it immediately without searching the right subtree.
        if (leftResult != null) {
            return leftResult;
        }

        // If not found in the left subtree, search in the right subtree.
        return getTargetCopy(original.right, cloned.right, target);
    }
}
```
### Algorithm
*   Define a recursive function, for example, `findCorresponding(originalNode, clonedNode, target)`.
*   **Base Case:** If `originalNode` is `null`, it means we've reached the end of a branch without finding the target, so return `null`.
*   **Check Target:** Compare the `originalNode` reference with the `target` reference (`originalNode == target`). If they are the same object, it means we've found the target in the original tree. The corresponding node is `clonedNode`, so we return it.
*   **Recurse Left:** Call the function recursively for the left children: `findCorresponding(originalNode.left, clonedNode.left, target)`. If this call returns a non-null node, it means the target was found in the left subtree. Propagate this result up by returning it immediately.
*   **Recurse Right:** If the left subtree search returned `null`, it means the target is in the right subtree. Call the function recursively for the right children: `findCorresponding(originalNode.right, clonedNode.right, target)` and return its result.
*   The initial call will be `getTargetCopy(original, cloned, target)`.

# Solutions
### CSharp

```csharp
/** * Definition for a binary tree node. * public class TreeNode { * public int val; * public TreeNode left; * public TreeNode right; * public TreeNode(int x) { val = x; } * } */ public class Solution { private TreeNode target ; public TreeNode GetTargetCopy ( TreeNode original , TreeNode cloned , TreeNode target ) { this . target = target ; return dfs ( original , cloned ); } private TreeNode dfs ( TreeNode original , TreeNode cloned ) { if ( original == null ) { return null ; } if ( original == target ) { return cloned ; } TreeNode left = dfs ( original . left , cloned . left ); return left == null ? dfs ( original . right , cloned . right ) : left ; } }
```

### Java

```java
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { private TreeNode target ; public final TreeNode getTargetCopy ( final TreeNode original , final TreeNode cloned , final TreeNode target ) { this . target = target ; return dfs ( original , cloned ); } private TreeNode dfs ( TreeNode root1 , TreeNode root2 ) { if ( root1 == null ) { return null ; } if ( root1 == target ) { return root2 ; } TreeNode res = dfs ( root1 . left , root2 . left ); return res == null ? dfs ( root1 . right , root2 . right ) : res ; } }
```

### CPP

```cpp
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: TreeNode * getTargetCopy ( TreeNode * original , TreeNode * cloned , TreeNode * target ) { function < TreeNode * ( TreeNode * , TreeNode * ) > dfs = [ & ]( TreeNode * root1 , TreeNode * root2 ) -> TreeNode * { if ( root1 == nullptr ) { return nullptr ; } if ( root1 == target ) { return root2 ; } TreeNode * left = dfs ( root1 -> left , root2 -> left ); return left == nullptr ? dfs ( root1 -> right , root2 -> right ) : left ; }; return dfs ( original , cloned ); } };
```

### Python

```python
# Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution : def getTargetCopy ( self , original : TreeNode , cloned : TreeNode , target : TreeNode ) -> TreeNode : def dfs ( root1 : TreeNode , root2 : TreeNode ) -> TreeNode : if root1 is None : return None if root1 == target : return root2 return dfs ( root1 . left , root2 . left ) or dfs ( root1 . right , root2 . right ) return dfs ( original , cloned )
```