# Java 101 Chapter 13

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

The following leetcode exercise is called:

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

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.

**Follow up:** Solve the problem if repeated values on the tree are allowed.

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

**Example 4:**

**Input:** tree = [1,2,3,4,5,6,7,8,9,10], target = 5

**Output:** 5

**Example 5:**

**Input:** tree = [1,2,null,3], target = 2

**Output:** 2

**Constraints:**

- The number of nodes in the
`tree`

is in the range`[1, 10^4]`

. - The values of the nodes of the
`tree`

are unique. `target`

node is a node from the`original`

tree and is not`null`

.

**Solution**

For my solution, I could not care less about the original three, instead, we focused on the main parts:

- What makes a node? A node is made up by their holding value, their child/leaves and the parents node or route. Since we do not know the parent route of the given node. We will ignore that property
- How would we traverse the three? Honestly, this is not as relevant, I used a queue and an iterative approach to traverse this three.

My solution in java can be seen below:

/**

* 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) {

//Queue<TreeNode> queue= new LinkedList<>

Queue<TreeNode> q = new LinkedList<TreeNode>();

q.add(cloned);

while(q.size() > 0){

TreeNode tmp = q.poll();

if( areNodeSame(target, tmp) ) return tmp;

if(tmp.left != null ) q.add(tmp.left);

if(tmp.right != null ) q.add(tmp.right);

}

return null;

}

public boolean areNodeSame(TreeNode node, TreeNode anotherNode){

if(node != null && anotherNode != null && node.val == anotherNode.val ){

if(node.left == null && anotherNode.left != null) return false;

if(node.left != null && anotherNode.left == null) return false;

if(node.left != null && anotherNode.left != null && node.left.val != anotherNode.left.val) return false;

if(node.right == null && anotherNode.right != null) return false;

if(node.right != null && anotherNode.right == null) return false;

if(node.right != null && anotherNode.right != null && node.right.val != anotherNode.right.val) return false;

return true;

}return false;

}

}