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

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.

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.

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).

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

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

Recursive DFS Approach

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’.

Time Complexity

O(N), where ‘N’ is the total number of nodes in the given binary tree.

In the worst case, we are exploring each node in the tree exactly once. Hence, the overall time complexity will be O(N).

Space Complexity

O(N), where ‘N’ is the total number of nodes in the given binary tree.

In the worst case, the recursion stack will store the ‘N’ number of a function call, where ‘N’ is the total number of nodes in a given tree. Hence, the overall space complexity will be O(N).

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

Problem statement

Sample Input 1:

Sample Output 1:

Explanation Of Sample Input 1:

Sample Input 2:

Sample Output 2:

Explanation Of Sample Input 2: