Node Level

Easy
0/40
Average time to solve is 15m
profile
Contributed by
40 upvotes
Asked in company
Microsoft

Problem statement

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.

Note:

Consider root to be at level 1. It is guaranteed that all the nodes in the binary tree have distinct values.
Detailed explanation ( Input/output format, Notes, Images )
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 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

1
3 8
5 2 7 -1
-1 -1 -1 -1 -1 -1
Explanation : 
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).
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:
1 3 8 5 2 7 -1 -1 -1 -1 -1 -1 -1
Output Format: 
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.
Note : 
You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints: 
1 <= T <= 5
0 <= N <= 3000
0 <= node data <= 10^9  

Time Limit: 1 sec
Sample Input 1:
2
1 2 3 -1 -1 -1  6 -1 -1
6
1 2 -1 -1 -1
1
Sample Output 1:
3
1
Explanation of Sample Input 1:
 For the first test case, the given binary tree is shown below.

1 Here, we see that node 6 is at a distance of 2 units from the root(node 1). Hence, our level will be 3.

For the second test case, the given binary tree is shown below.

1

As we are looking for node 1 which is itself the root node, hence our level is 1.
Sample Input 2:
1
1 3 8 5 -1 7 -1 -1 -1 -1 -1
10
Sample Output 2:
0
Explanation of Sample Input 2:
For the first test case, the given binary tree is shown below.

1

As node 10 is not present in the tree, so we return 0.
Hint

What is the distance between the root and node containing the specified value?

Approaches (2)
Depth-First Search

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.

 

Example 

E:\coding ninjas\Phase 2\problem 19 - Siblings in binary tree\3.png

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.

 

Algorithm :

 

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

 

 

Time Complexity

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

 

In the worst case, we visit each node exactly once in the DFS function that takes O(N) time.

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, when we have given a skew binary tree, we need O(N) extra space for the recursion stack of recursive calls.

Hence the overall space complexity will be O(N).

Code Solution
(100% EXP penalty)
Node Level
Full screen
Console