Level Leaf

Moderate
0/80
Average time to solve is 25m
profile
Contributed by
11 upvotes
Asked in companies
AmazonFlipkart limited

Problem statement

You are given a binary tree consisting of ‘N’ nodes. Ninja recently learned about tree algorithms and the teacher wants him to find whether all the leaves of the tree are at the same level.

A node is a leaf if it has neither the left child nor the right child.

If all the leaves are at the same level, output 1. Else, output 0.

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', representing the number of nodes in the tree.

The third 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 2
3 -1 4 5
-1 3 -1 -1 -1 -1
-1 -1

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

Level 2 :
Left child of 1 = 2
Value of left child of 1 = 2
Right child of 1 = 3
Value of right child of 1 = 2

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

Level 4 :
Left child of 4 = null (-1)
Right child of 4 = 7
Value of right child of 4 = 3
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, output 1 if all leaves are at the same level and 0 if not.

Print the output of each test case in a new line.
Note : 
You don’t need to print anything. It has already been taken care of. Just implement the given function.
Constraints : 
1 <= T <= 10
1 <= N <= 10^5
1 <= Value of node[i] <= 10^5
Sum of N over all Test cases <= 10^5
It is guaranteed that the given input is a binary tree.

Time Limit : 1 sec
Sample Input 1 :
2
3
1 2 3 -1 -1 -1 -1
4
1 2 3 4 -1 -1 -1 -1 -1
Sample Output 1 :
1
0
Explanation Of Sample Input 1 :
For test case 1 we have, 

Nodes 2 and 3 are the leaves of the tree and they are at the same level.


So, we output 1.

For test case 2 we have,

The input tree is : 


Nodes 3 and 4 are the leaves of the tree at different levels.

So, we output 0.
Sample Input 2 :
2
5
2 2 -1 3 1 -1 4 -1 -1 -1 -1 
4
4 1 -1 1 1 -1 -1 -1 -1
Sample Output 2 :
1
1
Hint

 Find the level of all the leaves.
 

Approaches (1)
Optimal Approach


Approach : 
 

  • Traverse the input tree in DFS maintaining the level of the current node.
  • For each vertex of the tree :
    • Check if this is the leaf of the tree.
    • If yes, check if the current level is the same for all previous leaves.
    • If not, return 0.
  • Return 1.


 

Algorithm : 
 

  • Initialise a global variable ‘level’ = -1.
  • Call a function ‘dfs’ from the root node with ‘l=0’ as parameter.
    • Check if the current node is the leaf node.
    • If yes, check if ‘level=-1’ , this is the first leaf node.
    • Update ‘level’ = ‘l’.
    • Check if ‘level’ = ‘l’ :
    • If not, return 0.
    • If the left child exists, call recursively ‘dfs’ on the left child and pass ‘l+1’ as the level for the child node.
    • Similarly call ‘dfs’ for the right child.
    • If ‘0’ is returned on call of any ‘dfs’ , return 0.
    • Return 1.
  • Return ‘dfs’ call response as result.
Time Complexity

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

We are traversing the node once, so the overall time complexity is O(N).

 

Space Complexity

O(1)
 

Constant extra space is required. Hence, the overall Space Complexity is O(1).

 

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