Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Problem Statement
2.1.
Complete Binary Tree
3.
Approach 1
3.1.
Algorithm
3.2.
Dry Run
3.3.
Implementation in C++
3.4.
Complexity Analysis
4.
Approach 2
4.1.
Algorithm
4.2.
Dry Run
4.3.
Implementation in C++
4.4.
Complexity Analysis
5.
Frequently Asked Questions
5.1.
What is a binary tree?
5.2.
What are the three common types of traversal techniques for a binary tree?
5.3.
What is the difference between depth-first and breadth-first traversal techniques?
5.4.
What is the time complexity of inorder, preorder, and postorder traversal techniques?
5.5.
What is the depth of a binary tree?
6.
Conclusion
Last Updated: Mar 27, 2024
Medium

Count Number of Nodes

Crack Google SDE interview : Essential projects
Speaker
Saurav Prateek
SDE-2 @
20 Jun, 2024 @ 01:30 PM

Introduction

In this blog, we will analyze a problem based on Binary Trees. Binary Trees have a lot of interesting properties, and in this blog, we will have a greater understanding of these properties. Problems based on binary trees are prevalent in coding interviews and programming contests. This article will discuss various approaches to counting the number of nodes in a complete binary tree.

OG Image

Now, let’s dive into the problem statement.

Problem Statement

Given the root of a complete binary tree, write a program to count the number of nodes.

Now the question comes - What do you mean by a complete binary tree?

Complete Binary Tree

A complete binary tree is one with all the levels filled except possibly the last one. In the last level, the nodes are as far left as possible. The number of nodes in the last level can be between 1 and 2^h, where h denotes the height of the last level.

The following examples will make the definition more clear.

Complete binary trees-1

                           

Complete binary trees-2

Complete Binary Trees

Not Complete Binary Tree-1

                   

Not Complete Binary Tree-2

Not Complete Binary Trees

Input

Consider the complete binary tree in the image given as input to the program.

Input BST Image

Output

Number of nodes: 5

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Approach 1

A straightforward approach would be to traverse the whole binary tree and count the number of nodes as we encounter a new node. Recursion is the most common way to traverse a binary tree using pointers. The base case of the recursion procedure will evaluate if the tree node in consideration is null.

Let us discuss the algorithm now.

Algorithm

  1. Create a recursive function count_number_of_nodes, which takes a tree node as a parameter.
  2. Base case: If the tree node is null, return 0.
  3. Otherwise, return 1 + the sum of the number of nodes in the left and right subtree.

Dry Run

Let us consider the above example, 

BST Image

Here, we need to find the total nodes in the tree.

Step-1

In the first step, we will make a DFS Algorithm call to the left subtree of node 1, and inside that call, it will further make calls to both the left and right subtree of node 2, so both calls will return 1 because they are single nodes. 

Step-1 Image

Step-2

In the second step, the call made to the left subtree of node 1 will return 3(1+left+right). Here, left and right are the calls made to the children of node 2, so at node 2, we would have 2, and from there, we will return (2+1).

Step-2 Image

Step-3

Now, a recursive call would be made to the right subtree of node 1, and it will return only 1 because it does not have any children.

Step-3 Image

So now, the total number of nodes would be left+right+1; here left is 3, and the right is 1, so the total nodes are equal to 3+1+1=5.

Implementation in C++

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

// Definition for a binary tree node.
struct Node
{
    // value stored in the node.
    int val;

    // left and right children.
    Node *left, *right;

    // to create a node with no children and val initialized with x.
    Node(int x) : val(x), left(nullptr), right(nullptr) {}
};

int count_number_of_nodes(Node *node)
{
    { // if there is no node.
        if (node == NULL)
            return 0;
    }

    // count number of nodes on the left.
    int left = count_number_of_nodes(node->left);

    // count number of nodes on the right.
    int right = count_number_of_nodes(node->right);

    // 1 -> to take into account the current node.
    return left + right + 1;
}

int main()
{

    Node *root = new Node(1);
    root->left = new Node(2);
    root->right = new Node(3);
    root->left->left = new Node(4);
    root->left->right = new Node(5);

    int number_of_nodes = count_number_of_nodes(root);
    cout << "Number of nodes: " << number_of_nodes << endl;
}

 

Output

Number of nodes: 5

Complexity Analysis

Time Complexity

The time complexity of the above algorithm is O(n), where n is the number of nodes in the tree.

It is because the program traverses every node in the tree.

Space Complexity

The space complexity of the above algorithm is O(log(n))

It is because the recursion can go at most log(n) deep. Hence the recursion stack can occupy O(log(n)) space in the worst case.

Approach 2

Can we improve the time complexity? Surely yes. Notice that we have not yet used the definition of the complete binary tree. 

Realize that we do not need to traverse the subtree of a tree node if we know that the leftmost node in the subtree is at the same depth as the rightmost node in the subtree. It would mean that the number of nodes in the subtree is equal to 2^h - 1, where h is the height of the tree node in consideration.

Let's code this approach.

Algorithm

  1. Left_height function: It takes a tree node as a parameter and calculates the depth of the leftmost node in the node's subtree. Put another way, this function returns the number of nodes in the path from the current node to the leftmost node in the current node's subtree.
  2. Right_height function: It takes a tree node as a parameter and calculates the depth of the rightmost node in the node's subtree.
  3. Create a recursive function that takes a tree node as a parameter. The base case of the function evaluates if the node is null.
  4. Otherwise, if the depth of the leftmost and rightmost nodes in the current node's subtree are equal, return 2^h - 1, where h is the height of the current node.
  5. If they are not equal, return left+right+1.

Dry Run

Step-1

In the first step, we will make a recursive call for a left subtree of node 1, and inside that recursive call, we will make calls to find the max height of the leftmost node and rightmost node. For node 2, left and right represent the max height of leftmost and rightmost nodes in their subtrees, which equals 2, so since both are the same, we would return pow(2, left)-1 = {(pow(2,2)-1) = 3}.

Step-1 Image

Step-2

In the second step, we will return to the root node 1 and make a recursive call for the right subtree. Since there is only one node, it will return 1; now we can see that left=3, which was obtained in the last step, and right=1 since both are not the same, so we will return (left+right+1). 

Step-2 Image

Step-3 

Now we will print the obtained result from the function, i.e., we will print 5.

Step-3 Image

Implementation in C++

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

// Definition for a binary tree node.
struct Node
{
    // value stored in the node.
    int val;

    // left and right children.
    Node *left, *right;

    // to create a node with no children and val initialised with x.
    Node(int x) : val(x), left(nullptr), right(nullptr) {}
};

// to find out max height of left subtree
int left_height(Node *node)
{

    // return 0 if the node is null.
    if (node == NULL)
        return 0;

    // return the depth of the left children + 1.
    return 1 + left_height(node->left);
}

// to find out max height of right subtree
int right_height(Node *node)
{

    // return 0 if the node is null.
    if (node == NULL)
        return 0;

    // return the depth of the right children + 1.
    return 1 + right_height(node->right);
}

int count_number_of_nodes(Node *node)
{
    // if there is no node.
    if (node == NULL)
        return 0;

    // calculate depth of the leftmost node in the subtree.
    int l_height = left_height(node);

    // calculate depth of the rightmost node in the subtree.
    int r_height = right_height(node);

    // if they are equal
    if (l_height == r_height)
        return (int)pow(2, l_height) - 1;

    // otherwise, go by the general approach.
    return 1 + count_number_of_nodes(node->left) + count_number_of_nodes(node->right);
}

int main()
{

    Node *root = new Node(1);
    root->left = new Node(2);
    root->right = new Node(3);
    root->left->left = new Node(4);
    root->left->right = new Node(5);

    int number_of_nodes = count_number_of_nodes(root);
    cout << "Number of nodes: " << number_of_nodes << endl;
}

 

Output

Number of nodes: 5

Complexity Analysis

Time Complexity

The time complexity of the above algorithm is O(log(n) * log(n)). The time complexity of the left_height and right_height functions is log(n), where n is the number of nodes in the binary tree.

We calculate the height of the current node at each stage of the recursive procedure. And using the approach defined above, we need to consider only one node at each binary tree level. Why? 

If the current node does not satisfy the proposed equality condition, then at least one of its children must satisfy it. It is because all the nodes in a complete binary are as far left as possible.

Since the height of a complete binary tree is of the order of O(log(n)), the total time complexity will be (log(n) * log(n)).

Space Complexity

The space complexity of the above algorithm is the same as Approach 1, i.e., log(n).

In this approach as well, the depth of the recursion stack can be at most log(n) in the worst case.

Frequently Asked Questions

What is a binary tree?

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

What are the three common types of traversal techniques for a binary tree?

The three common traversal techniques for a binary tree are inorder, preorder, and postorder traversal.

What is the difference between depth-first and breadth-first traversal techniques?

Depth-first traversal techniques, such as inorder, preorder, and postorder traversal, explore the depth of a binary tree before visiting nodes at a higher level. Breadth-first traversal techniques, such as level-order traversal, explore nodes at each level before moving on to nodes at a deeper level.

What is the time complexity of inorder, preorder, and postorder traversal techniques?

The time complexity of inorder, preorder, and postorder traversal techniques is O(n), where n is the number of nodes in the binary tree. This is because each node in the tree is visited exactly once.

What is the depth of a binary tree?

The depth of a binary tree is the length of the longest path from the root node to any leaf node in the tree. 

Also Read - Strong number in c

Conclusion

This article explained different ways to count the number of nodes in a complete binary tree. I hope that the time complexity of Approach 2 is understandable. The algorithms used the concept of the height of a tree quite profoundly.  

Yet learning never stops, and there is a lot more to learn.

I hope this blog has helped you enhance your knowledge regarding the above Data Structures and Algorithms problem, and if you want to learn more, check out our articles on Coding Ninjas Studio. Enroll in our coursesrefer to the test series and problems available, and look at the interview bundle for placement preparations.

Nevertheless, you may consider our paid courses to give your career an edge over others!

Until then, All the best for your future endeavors, and Keep Coding.

Previous article
Count subtrees that sum up to a given value x only using a single recursive function
Next article
Count of leaf nodes required to be removed at each step to empty a given Binary Tree
Live masterclass