How to count the number of nodes in a complete binary tree

Introduction

This blog will discuss how to count the total number of nodes in a complete binary tree If we are given its root. For example, consider the tree shown below. If we count the total number of nodes in it, the answer will be 12. 

There could be many ways to count the number of nodes in a complete binary tree, but we will learn only a few of them. But before moving straight to the solution, let's refresh our knowledge of binary and complete binary trees.

A binary tree is a tree in which all the nodes can have at most two children, and a complete binary tree is a tree in which all the levels must be filled except the last level, which is filled from left to right direction. 

For example, in the figure below, the tree on the left is a complete binary tree. But, the tree on the right is not a complete binary tree.

The basic solution to this problem is to traverse through the tree and count the number of nodes. And, the efficient approach uses the relation between height and number of nodes in the complete binary tree. So let's begin with the basic approach -

Basic approach

The basic approach to this problem is quite simple. We perform the DFS traversal of the binary tree and keep a count of the notes we encounter during the traversal.

Algorithm

  • Construct a complete binary tree or take it from user input.
  • Create a function to count the number of nodes in the tree. It takes the root of the tree as an argument and returns the number of nodes.
  • If the root is null in the count function, return 0; otherwise, return the sum of the number of nodes in the left, right subtree, and one.

Implementation

#include <bits/stdc++.h>
using namespace std;
//Class for the nodes of a tree.
class treenode {
public:
    int value;
    treenode* left;
    treenode* right;


    treenode(int num)
    {
        value = num;
        left = nullptr;
        right = nullptr;
    }
};
//Function to count nodes in a complete binary tree.
int count(treenode* root)
{
    //Base case.
    if (!root)
    {
        return 0;
    }
    return 1 + count(root->left) + count(root->right);
}
//Driver function.
int main()
{
    treenode* root = new treenode(12);
    root->left = new treenode(11);
    root->right = new treenode(10);
    root->left->left = new treenode(9);
    root->left->right = new treenode(8);
    root->right->left = new treenode(7);
    root->right->right = new treenode(6);
    root->left->left->left = new treenode(5);
    root->left->left->right = new treenode(4);
    root->left->right->left = new treenode(3);
    root->left->right->right = new treenode(2);
    root->right->left->left = new treenode(1);
    cout<<"The total number of nodes in this complete binary tree is- " <<count(root)<<endl;
    return 0;
}

 

Output- 

The total number of nodes in this complete binary tree is- 12

Complexity Analysis

Time complexity - O(N).

Space complexity - O(1).

Efficient approach

In this method, we use the property of a complete binary tree that the total number of nodes in a full complete binary tree is 2h-1. By definition, a complete tree must be filled up to the second last level, as the last level may or may not be filled, but all the leaf nodes will be on as much left position as possible.

So we will start with the root and calculate the tree's height in both the left and right directions. If both the height are equal, then the number of nodes will 2h-1. Otherwise, we will repeat the process for left and right subtrees and return the sum of (nodes in left subtree) + (nodes in right subtree)+1(for the root) as the count.

Algorithm

  • Construct a complete binary tree or take it from user input.
  • Create a function to count the number of nodes in the complete binary tree. It takes the root of the tree as an argument and returns the number of nodes.
  • Count function calculates the left height and the right height of the tree if both heights are equal, then returns 2h-1 as no. of nodes, else makes a recursive call to count Function for left and right subtree and returns the sum of (nodes in left subtree) + (nodes in right subtree)+1(for the root). 

Implementation in C++

#include <bits/stdc++.h>
using namespace std;
//Class for the node s ofa tree.
class treenode {
public:
    int value;
    treenode* left;
    treenode* right;


    treenode(int num)
    {
        value = num;
        left = nullptr;
        right = nullptr;
    }
};
//Function to calculate the left height of the complete binary tree
int lheight(treenode* root)
{
    int lh=0;
    while(root)
    {
        lh++;
        root=root->left;
    }
    return lh;
}
//Function to calculate the right height of the complete binary
//tree.
int rheight(treenode* root)
{
    int rh=0;
    while(root)
    {
        rh++;
        root=root->right;
    }
    return rh;
}
//Function to count nodes in a complete binary tree.
int count(treenode* root)
{
    //Base case.
    if (!root)
    {
        return 0;
    }
    //Function call for left height.
    int lh=lheight(root);
    //Function call for right height.
    int rh=rheight( root);
    //For fully filled complete binary subtrees.
    if(lh==rh)
    {
        return(1<<lh)-1;
    }
    //Else, count the number of nodes in the sub trees.
    return 1 + count(root->left) + count(root->right);
}
//Driver function.
int main()
{
    //Creating the complete binary tree.
    treenode* root = new treenode(12);
    root->left = new treenode(11);
    root->right = new treenode(10);
    root->left->left = new treenode(9);
    root->left->right = new treenode(8);
    root->right->left = new treenode(7);
    root->right->right = new treenode(6);
    root->left->left->left = new treenode(5);
    root->left->left->right = new treenode(4);
    root->left->right->left = new treenode(3);
    root->left->right->right = new treenode(2);
    root->right->left->left = new treenode(1);
    cout<<"Total number of nodes in this complete binary tree is- " <<count(root)<<endl;
    return 0;
}

 

Output- 

The total number of nodes in this complete binary tree is- 12

Complexity Analysis

Time complexity - O((logN)2) because O(logN) will be the time complexity of finding the height of the binary tree, and  O(logN) will be the time complexity of the traversal of the binary tree, as most of the nodes will fall under the category whose left and right height is equal.

Space complexity - O(logN) for the recursive call stack.

Frequently asked questions

  1. What is a binary tree?
    A tree in which every node can have at most two children is called a binary tree.
  2. What is a complete binary tree?
    A binary tree in which all the levels are filled, possibly except the last level. Also, the nodes in the last level are filled towards as left as possible.
  3. What is a filled complete binary tree?
    A complete binary tree in which even the last level is filled is known as a filled complete binary tree.
  4. What is the relation between height and the number of nodes in a complete binary tree?
    In a complete binary, the total number of nodes, if it is filled, is 2height-1. 
  5. How many leaf nodes are there in a filled complete binary tree?
    The number of leaf nodes in a filled complete binary tree will be 2h-1.

Key takeaways

In this blog, we learned about them, methods we can use to find the total number of nodes in a complete binary tree-

  • We started with the basic approach that traverses through the whole tree to count the number of nodes. In this blog, we used preorder-based DFS traversal. But this approach can be implemented using any traversal,
  • The second approach was based on the relation between the height and number of nodes in a complete binary tree; if the height of a filled binary tree is h, then the total number of nodes in it will be 2h-1. So we start the root to check if the left height or right tree of the binary tree is the same. If both of them are equal, then we returned the number of nodes as 2h-1 else, repeat the process individually for the left and right subtree using recursion and return the sum of nodes in the left subtree, nodes in right sub tree+1(for the root).

You can learn more about binary trees here. Also, don’t forget to practice similar problems on Code studio.

Was this article helpful ?
0 upvotes

Comments

No comments yet

Be the first to share what you think