Home » Interview coding problems/challenges

Count Number of Nodes in a Complete Binary Tree (Leetcode Problem Solution)

In this article, we are going to see how to find the number of nodes in a complete binary tree efficiently? This problem has also been featured in the Google interview round.
Submitted by Radib Kar, on August 01, 2020

Prerequisite: Complete Binary Tree

Problem statement:

Find number of nodes in a complete Binary Tree.

Examples:

The above binary Tree is a complete binary tree and has number of nodes = 4

Solution:

In a complete binary tree every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible. A complete Binary Tree can have between 1 and 2^h nodes inclusive at the last level h.

So, the properties of complete Binary tree is:

All levels are filled up except the last level
The nodes at the last levels are as far left as possible

Now to find the number of nodes we can solve in two ways.

1) Naïve approach in O(n)

We can find the number of nodes recursively like for any binary tree.

The number of nodes in the tree= 1+ Number of nodes in the left subtree + Number of nodes in the right subtree. Below is the definition of the recursive function:

int no_of_nodes(TreeNode root){
    if (root is NULL)
        return 0
    return 1+ no_of_nodes(root->left)+ no_of_nodes(root->right)
}

C++ Implementation:

#include <bits/stdc++.h>
using namespace std;

class TreeNode {
public:
    int val;
    TreeNode* left;
    TreeNode* right;

    TreeNode(int v)
    {
        val = v;
        left = NULL;
        right = NULL;
    }
};

//calculate number of nodes in 
//the complete tree recursively
int countNodes(TreeNode* root)
{
    if (!root)
        return 0;
    return 1 + countNodes(root->left) + countNodes(root->right);
}

int main()
{
    cout << "Tree which is both complete and full in example 4\n";
    
    TreeNode* root = new TreeNode(1);
    
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    root->left->right = new TreeNode(5);
    
    cout << "Number of nodes in this tree: " << countNodes(root) << endl;
    
    return 0;
}

Output:

Tree which is both complete and full in example 4
Number of nodes in this tree: 5

2) Efficient method using complete binary tree properties

We can count the total number of nodes using complete tree properties:

Say, the total number of nodes is n

And the height of the complete binary tree is: h

Then it’s guaranteed that all levels up to height h-1 is completed which means has 2^h-1 number of nodes up to the last level. At the last level say there r k number of nodes which are as left as much possible. So, we total no of nodes n= k+ 2^h-1

So, we need to find two things:

Height of the tree
Number of nodes at the last level

Height of the tree can be found in O(Log₂n) time and we can find k also in logarithmic time complexity using the fact that all the nodes at last level lies as left as far possible.

The algorithm is like below:

If root is NULL return 0
Compute the height of the tree, h.
If height is 1 then return 1 (Only root is there)
As we discussed earlier that all the levels except the last one completed and has 2^h-1 number of nodes. We can compute that in constant time as we already know h. Now, we have to calculate number of nodes at the last level, k. The number of nodes in the last level can be anything between 1 to 2^h. Now to find out exact number of nodes, we perform the binary search like the below implementation by the node index to check how many nodes are in the last level. Say the function is is_exists which takes number of nodes we expect to be at last level, height of tree and returns true or false. It returns true if the last level has same more nodes that we expected and returns false if the last node has less number of notes than expected. We can find this also in logarithmic time as shown as in the implementation (It's possible because of the fact that all nodes are as left as far possible in the last level for complete binary tree). So overall complexity for finding number of nodes is O(logn)*O(logn)

So over all time complexity is O(logn) (to find height and number of nodes in all levels except the last one)+O(logn)² (to find number of nodes in the last level)

C++ Implementation:

#include <bits/stdc++.h>
using namespace std;

class TreeNode {
public:
    int val;
    TreeNode* left;
    TreeNode* right;

    TreeNode(int v)
    {
        val = v;
        left = NULL;
        right = NULL;
    }
};

bool is_exists(TreeNode* root, int h, int no_of_nodes)
{
    TreeNode* cur = root;

    int left = 0, right = pow(2, h) - 1;
    //loop runs for h=O(logn) time
    //binary search to find the 
    //no_of_nodes th node exist or not
    for (int i = 0; i < h; ++i) {
        int mid = left + (right - left) / 2;
        if (no_of_nodes <= mid) {
            cur = cur->left;
            right = mid;
        }
        else {
            cur = cur->right;
            left = mid + 1;
        }
    }
    //if no_of_nodes at last level exists 
    //then cur will point to that no_of_nodes th node
    //else NULL
    return cur != NULL;
}

//since it's a complete tree we can traverse 
//towards the left child always
//since the last level nodes will be as 
//left as far possible
int height(TreeNode* root)
{
    if (!root)
        return 0;
    TreeNode* cur = root;
    int count = 0;
    while (cur) {
        count++;
        cur = cur->left;
    }
    return count;
}

//calculate number of nodes in 
//the complete tree efficiently
int countNodes(TreeNode* root)
{
    if (!root)
        return 0;
    if (!root->left && !root->right)
        return 1;

    int h = height(root) - 1;
    //number of nodes except the last level 
    //is calculated as follow
    int no_of_nodes_except_last_level = pow(2, h) - 1;
    //number of possible nodes at the last level
    int left = 1, right = no_of_nodes_except_last_level;

    int last_level_nodes;
    //do binary search to check 
    //if predicted number of node exists or not
    while (left <= right) {
        int mid = left + (right - left) / 2;
        //finds if last level has mid number of nodes or not
        if (is_exists(root, h, mid)) {
            left = mid + 1;
        }
        else
            right = mid - 1;
    }
    last_level_nodes = left;
    return no_of_nodes_except_last_level + last_level_nodes;
}

int main()
{
    cout << "Tree which is both complete and full in example 4\n";
    
    TreeNode* root = new TreeNode(1);
    
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    root->left->right = new TreeNode(5);
    
    cout << "Number of nodes in this tree: " << countNodes(root) << endl;
    
    return 0;
}

Output:

Tree which is both complete and full in example 4
Number of nodes in this tree: 5

Also tagged in: Google

Comments and Discussions!

Load comments ↻