# Find a Corresponding Node of a Binary Tree in a Clone of That Tree- Leetcode (Medium Level)

**January Leetcode Challenge**

**Question:**

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.

Solve the problem if repeated values on the tree are allowed.

## Intuition:

- Transverse through the
*Cloned*binary tree and if the value of any node in the*Cloned*tree is equal to target node’s value, return that node of*Cloned*tree. This solution would be correct if all the node values are*unique*. - Map every node of the
*Cloned*tree with its corresponding*Original*tree node. Where key is the*Original*tree’s node and the value is the C*loned*tree’s node. Finally return the value from the map at the target node given in the problem. This is the correct solution for this problem and I will be providing my code for this approach below in C++;

/**

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

unordered_map<TreeNode*, TreeNode*> ma; //inorder traversal of binary tree;

void fillMap(TreeNode* original, TreeNode* cloned){

if(!original)return;

fillMap(original->left,cloned->left);

ma[original]=cloned;

fillMap(original->right,cloned->right);

}

public:

TreeNode* getTargetCopy(TreeNode* original, TreeNode* cloned, TreeNode* target) {

fillMap(original,cloned);

return ma[target];

}

};

Input is taken by the Leetcode compiler and struct TreeNode{}; was also by default created by Leetcode compiler; we just have to implement the function “*getTargetCopy()”*;

I used

unordered_mapinstead of normalmapbecauseunordered_mapis faster than map and I didn’t wanted my keys to be sorted.

mapkeeps keys values in sorted order butunordered_mapdoesn’t.

For this I have created a private unordered_map and a *fillMap()* function. I performed inorder traversal recursively on both trees to fill my map with correct values and then finally returned my target value from map in *getTargetCopy()* function;

Time and space complexity of the above solution are:

**Time complexity** is *O(n)* and **Space complexity** in *O(n)*, where *n* is the number of nodes in the tree.