Last Updated: 15 Mar, 2021
Find a Corresponding Node of a Binary Tree in a Clone of That Tree
Easy
Asked in companies
You have been given two exact same binary tree structures say ‘originalTree’ and ‘cloneTree’ and a reference to one of the nodes in ‘originalTree’.
You need to find the reference of the node in ‘cloneTree’, with the same value as the given node.
Note:
1. ‘cloneTree’ is an exact copy of the ‘originalTree’.
2. All nodes in ‘originalTree’ are distinct.
3. The given node in the ‘originalTree’ will not be NULL.
4. You cannot change any of the two given trees.
Input Format:
The first line contains an integer 'T' which denotes the number of test cases or queries to be run.
The first line of each test case contains elements of the tree in the level order form. The line consists of values of nodes separated by a single space. In case a node is null, we take -1 in its place.
The second line contains an integer ‘K’ which denotes the value of the reference node in ‘originalTree’.
For example, the level order input for the tree depicted in the below image.
50
13 72
3 25 66 -1
-1 -1 -1 -1 -1 -1
Explanation :
Level 1 :
The root node of the tree is 50
Level 2 :
Left child of 50 = 13
Right child of 50 = 72
Level 3 :
Left child of 13 = 3
Right child of 13 = 25
Left child of 72 = 66
Right child of 72 = ‘Null’
Level 4 :
All children are ‘Null’
The first not-null node(of the previous level) is treated as the parent of the first two nodes of the current level. The second not-null node (of the previous level) is treated as the parent node for the next two nodes of the current level and so on.
The input ends when all nodes at the last level are null(-1).
Note :
The above format was just to provide clarity on how the input is formed for a given tree.
The sequence will be put together in a single line separated by a single space. Hence, for the above-depicted tree, the input will be given as:
50 13 72 3 25 66 -1 -1 -1 -1 -1 -1 -1
Output Format:
For each test case, the output will be “1” if you have returned the correct node in ‘cloneTree’, else it will be “0”.
The output of each test case will be printed in a separate line.
Note :
You do not need to input or print anything, and it has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 5
1 <= N <= 3000
1 <= data <= 10 ^ 9
1 <= K <= 10 ^ 9
Where ‘data’ is the value of the nodes of the given binary tree, and ‘K’ represents the value of the given reference node in ‘originalTree’.
For a single test case, all given ‘data’ are distinct from each other and ‘K’ is equal to one given of ‘data’.
Time Limit: 1 Sec
Approaches
We need to find a node in the clone tree with a value equal to the value of the given node in the original tree. For this, we can traverse all the nodes in the clone tree and return the reference of a node with the required value.We will use the recursive Depth First Search traversal method to traverse all nodes in a given tree.
DFS Traversal: we traverse the below tree in this order - [ 7, 3, 5, 4, 1, 9 ].
Refer below diagram for better understanding.
Algorithm:
- Call ‘dfs’ with ‘ROOT’ = root node of given clone tree and value of the given node and store the returned node in a variable say ‘ANSNODE’
- Return ‘ANSNODE’
Description of ‘dfs’ function:
The function will take two parameters:
- ‘ROOT’: Root node of the tree that is to be traversed.
- ‘VAL’: Integer value to search the node with value ‘VAL’.
TreeNode dfs ( ‘ROOT’, ‘K’ ):
- Declare a ‘NODE’ variable say ‘TEMPNODE’ with ‘NULL’ value.
- Base case - If value of root node is same as given value.
- Return root node.
- Else:
- If ‘ROOT -> LEFT’ is not ‘NULL’, then call the recursive function with ‘ROOT’ = ‘ROOT -> LEFT’ and store the returned value in ‘TEMPNODE’.
- If ‘TEMPNODE’ is ‘NULL’ and ‘ROOT -> RIGHT’ is not ‘NULL’, call the recursive function with ‘ROOT’ = ‘ROOT -> RIGHT’ and store the returned value in ‘TEMPNODE’.
- Return ‘TEMPNODE’.
The idea here is to traverse the ‘cloneTree’ and once we reach a node with the given value, we can just simply return this node. For traversing the tree we can use BFS algorithm.
BFS traversal: we traverse the below tree in this order - [ 7, 3, 1, 5, 4, 9 ].
Algorithm:
- Declare a queue to store the nodes that are visited but not explored.
- Push the root node into the queue.
- Run a loop until the queue is not empty.
- Pop a front node from the queue and store it in a variable say ‘CURRNODE’.
- If the value of ‘CURRNODE’ is equal to the given node value.
- Return ‘CURRNODE’.
- Else
- Push all children of ‘CURRNODE’ into the queue.
Similar problems