Nodes In Complete Binary Tree

Moderate

0/80

Average time to solve is 15m

Contributed by

15 upvotes

+5 more companies

Problem statement

You are given the root of a complete binary tree, you need to calculate the number of nodes in the given complete binary tree.

A complete binary tree is a tree in which all the levels are completely filled except the last level. Nodes in the last level are as left as possible.

For Example:

In the above complete binary tree, all the levels are filled except for the last. In the last level, all the nodes in the last level are as far left as possible.

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. Then the test cases follow.

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.

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

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)

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

Output Format:

Return the number of nodes of the given complete 
binary tree.

Constraints:

1 <= T <= 10
0 <= Number of nodes in tree <= 10^5
1 <= Nodes Value <= 5*10^5

Time Limit: 1 second

Sample Input 1:

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

Sample Output 1:

Explanation For Sample Input 1:

For the above test case, the given tree is:

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 = 5
Left child of 3 = 7
Right child of 3 = 6

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

Hence the total number of nodes in the given tree is 7.

Sample Input 2:

1
5 6 7 10 -1 -1 -1 -1 -1

Sample Output 2:

Console