Day 17 : Count Leaf Nodes

Easy
0/40
Average time to solve is 10m
profile
Contributed by
86 upvotes
Asked in companies
SamsungOlaSlice

Problem statement

You are given a Binary tree. You have to count and return the number of leaf nodes present in it.

A binary tree is a tree data structure in which each node has at most two children, which are referred to as the left child and the right child

A node is a leaf node if both left and right child nodes of it are NULL.

Detailed explanation ( Input/output format, Notes, Images )
Input format : 
The first line of input contains an integer 'T' representing the number of the test case. Then the test case follows.

The first line of each test case contains elements of the binary tree in the level order form. The input consists of values of nodes separated by a single space in a single line. In case a node is null, we take -1 in its place.

For example, the input for the tree depicted in the below image would be :

example

20
10 35 
5 15 30 42 
-1 13 -1 -1 -1 -1 -1 
-1 -1

Explanation :

Level 1 :
The root node of the tree is 20

Level 2 :
Left child of 20 = 10
Right child of 20 = 35

Level 3 :
Left child of 10 = 5
Right child of 10 = 15
Left child of 35 = 30
Right child of 35 = 42

Level 4 :
Left child of 5 = null (-1)
Right child of 5 = null (-1)
Left child of 15 = 13
Right child of 15 = null (-1)
Left child of 30 = null (-1)
Right child of 30 = null (-1)
Left child of 42 = null (-1)
Right child of 42 = null (-1)

Level 5 :
Left child of 13 = null (-1)
Right child of 13 = 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: Here in this tree nodes 20, 10, 35, 15 are internal nodes as these Nodes have AT LEAST ONE CHILD NODE. While nodes 5, 30, 42, 13 are leaf nodes because they have NO CHILD NODES
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:
20 10 35 5 15 30 42 -1 13 -1 -1 -1 -1 -1 -1 -1
Input Format 
The first line of input contains an integer ‘T’ denoting the number of test cases to run. Then the test case follows.

For each test case, you will be given a reference to the root node.
Output Format 
For each test case, return the number of leaf nodes present in the binary tree.
Note: 
You do not need to print anything; it has already been taken care of. Just implement the given function.
Constraints: 
1 <= T <= 100
1 <= N <=10^3
1 <= data <= 10^9

Time Limit : 1 sec
Sample Input 1:
3
1 -1 -1
1  2  3  -1 -1 -1 4 -1 -1
1  2 -1 -1 3 -1 4 -1 -1
Sample Output 1:
1
2
1
Explanation For Sample Input 1:
(i) 1 is the only node present in the tree, and hence it is the only leaf node.
(ii) 2 and 4 are two leaf nodes present in the tree; all other nodes have at least one child (1 has 2 and 3 and 3 has 4).
(iii) 4 is the only leaf node present in the tree as all other nodes have at least one child node (1 has 2, 2 has 3 and 3 has 4)
Sample Input 2:
3
1 2 3 4 5 6 7 -1 -1 -1 -1 -1 -1 -1 -1
1 -1 2 -1 3 -1 -1
1 2 -1 3 4 5 6 7 8 -1 - 1 -1 -1 -1 -1 -1 -1
Sample Output 2:
4
1
4
Explanation For Sample Input 2:
(i) 4, 5, 6 and 7 are 4 leaf nodes present in the tree, all other nodes have at least one child (1 has 2 and 3, 2 has 4 and 5 and 3 has 6 and 7).
(ii) 3 is the only leaf node present in the tree as all other nodes have at least one child node (1 has 2 and 2 has 3)
(iii) 5, 6, 7 and 8 are 4 leaf nodes present in the tree, all other nodes have at least one child (1 has 2, 2 has 3 and 4, 3 has 5 and 6 and 4 has 7 and 8).
Hint

Try thinking of how you can use recursion to traverse through the binary tree and find leaf nodes.

Approaches (2)
Recursive

Let’s define a function COUNTLEAVES that take tree node ROOT as a parameter and do:

 

  1. If ROOT is null, return 0.
  2. If ROOT.LEFT and ROOT.right are both null, return 1.
  3. Initialize COUNT as COUNTLEAVES (ROOT.LEFT) + COUNTLEAVES (ROOT.RIGHT).
  4. Return COUNT.
Time Complexity

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

 

As we’ll be traversing each node once, for N nodes time complexity will be O(N).

Space Complexity

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

 

As we are using recursion and there can be maximum N nodes stored in the recursion stack. Hence the space complexity will be O(N).

Code Solution
(100% EXP penalty)
Day 17 : Count Leaf Nodes
Full screen
Console