King Nodes In Binary Tree

Moderate
0/80
Average time to solve is 20m
profile
Contributed by
2 upvotes
Asked in company
Microsoft

Problem statement

You have been practicing on the topic binary tree for few days. Your friend challenged you by giving you a binary tree and asks you to find the number of King nodes. A node with value ‘N’ is King if no node has a value greater than ‘N’ in the path from the root to it.

Note :

1. Two nodes may have the same value associated with it.
2. The root node will be fixed and will be provided in the function.
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line of the input contains a single integer 'T', representing the number of test cases.

The first line of each test case contains an integer 'N', which denotes the number of nodes in the tree.

The second line of each test case will contain the values of the nodes of the tree in the level order form ( -1 for 'NULL' node) Refer to the example for further clarification.
Example : 
Consider the binary tree


The input of the tree depicted in the image above will be like : 

1
2 3
4 -1 5 6
-1 7 -1 -1 -1 -1
-1 -1

Explanation :
Level 1 :
The root node of the tree is 1

Level 2 :
Left child of 1 = 2
Right child of 1 = 3

Level 3 :
Left child of 2 = 4
Right child of 2 = null (-1)
Left child of 3 = 5
Right child of 3 = 6

Level 4 :
Left child of 4 = null (-1)
Right child of 4 = 7
Left child of 5 = null (-1)
Right child of 5 = null (-1)
Left child of 6 = null (-1)
Right child of 6 = null (-1)

Level 5 :
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).
Output Format : 
For each test case, print a single integer representing the number of King nodes.

Print the output of each test case 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 <= 10
1 <= N <= 5*10^3

Time Limit : 1 sec
Sample Input 1 :
2
5
1 2 3 4 5 -1 -1 -1 -1 -1 -1
3
2 3 1 -1 -1 -1 -1
Sample Output 1 :
5
2
Explanation For Sample Input 1 :
For first test case the tree will be :


Node 1 : (1) path has maximum value as 1 itself.
Node 2 : (1 2)  path has maximum value as 2.
Node 3 : (1 3) path has maximum value as 3.
Node 4 : (1 2 4) path has maximum value as 4.
Node 5 : (1 2 5) path has maximum value as 5.
So, the total number of King nodes is 5.  

For second test tree will be :


Node 2 : (2) path has maximum value as 2 itself.
Node 3 : (2 3)  path has maximum value as 3.
Node 1 : (2 1) path has maximum value as 2.
So, the total number of King nodes is 2.
Sample Input 2 :
2
3
1 5 -1 2 -1 -1 -1
4 
3 4 8 1 -1 -1 -1 -1 -1
Sample Output 2 :
2
3
Hint

Think of traversing each path.

Approaches (1)
Depth - First Search

The basic idea is to use dfs and traverse paths recursively. We will keep the maximum value while traversing. If the current node's value is greater than the maximum node, then we have found a King node.
 

Here is the algorithm :
 

We will create a DFS function that will count the number of King nodes.

 

  1. Create a variable (say, ‘MX’) which will be used for assigning maximum values of paths and initialize it with ‘INT_MIN’.
  2. Call the DFS function.
     

DFS(‘ROOT’, ‘MX’)

 

  1. Create a variable (say, ‘COUNT’) that will store the count of King nodes and initialize it with 0.
  2. Check if ‘ROOT’ is equal to ‘NULL’, return.
  3. Check if ‘ROOT.DATA’ is greater than equal to ‘MX’
    • Increment ‘COUNT’ by 1.
    • Update ‘MX’ as the maximum of ‘MX’ and ‘ROOT.DATA’.
  4. Recursively traverse to the left and right of ‘ROOT’.
Time Complexity

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

 

We traverse all the nodes of the binary tree to traverse all the paths. Therefore, the overall time complexity will be O(N).

Space Complexity

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

 

Recursive stack can contain at most ‘N’ nodes of the binary tree .Therefore, the overall space complexity will be O(N).

Code Solution
(100% EXP penalty)
King Nodes In Binary Tree
Full screen
Console