Ninja has been given a binary tree having N nodes and an integer M, he needs to find the level of node M. He finds it difficult to solve and asks for your help.
Consider root to be at level 1. It is guaranteed that all the nodes in the binary tree have distinct values.
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 of each test case contains one integer ‘M’ denoting the node whose level has to be calculated. For example, the input for the tree depicted in the below image.
1 3 8 5 2 7 -1 -1 -1 -1 -1 -1 -1
Level 1 : The root node of the tree is 1 Level 2 : Left child of 1 = 3 Right child of 1 = 8 Level 3 : Left child of 3 = 5 Right child of 3 = 2 Left child of 8 =7 Right child of 8 = null (-1) Level 4 : Left child of 5 = null (-1) Right child of 5 = null (-1) Left child of 2 = null (-1) Right child of 2 = null (-1) Left child of 7 = null (-1) Right child of 7 = null (-1) 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: 1 3 8 5 2 7 -1 -1 -1 -1 -1 -1 -1
For each test case, return a single line containing the level specified by the node. If the node is not present, return 0. The output of each test case will be printed in a separate line.
You do not need to print anything, it has already been taken care of. Just implement the given function.
1 <= T <= 5 0 <= N <= 3000 0 <= node data <= 10^9 Time Limit: 1 sec
Here, we shall declare a recursive function that will stand at a particular node and check whether the current node’s value is equal to the value we are looking for. If it happens to be so, we will return 1 to our parent function. If not so, then will recursively call the child node of the current node and ask them to find the searched value. This recursive function will start from the root node and check all the nodes of the tree.
In the above figure, for example, if we were searching for node 8, then the recursive function would be called first on the root node .i.e 1. As the root node’s value is not the searched value, then will ask his child node 3 and 8 for the search. Recursively after going through nodes 3 and 5, when we reach node 8, we will stop calling recursive functions anymore and start returning 1 to our parent function. The current parent of 8 will add 1 to the level he received and send it to his parent. The following system is maintained till we reach the root node that will give us the output.
So, we will use a Depth-first search to find the level of the searched node.
- We declare a dfs function ‘level(node, searchedValue)’ with parameters as the root node and the searched value whose level has to be calculated. The return type of the function is an integer specifying the level. This function will be called from the main function and the value we receive is returned as the program output.
- First will be checking whether the current node exists or not. If not, we shall return 0 to our parent function.
- If our current node’s value is equal to the value we are looking for
- we shall return 1 and stop the function call to the child nodes.
- If not, we will ask our left child to find the ‘searchedValue’ by calling the function level(node -> left, ‘searchedValue’).
- If our left child does not return a positive number, we will look forward towards our right child node and check whether we get a positive number or not from the right child.
- Otherwise, we shall return 0 indicating that the ‘searchedValue’ is not present between the current node and all its child nodes.