Count Number of Nodes

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, 

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-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-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.

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;
}

You can also try this code with Online C++ Compiler

Run Code

Output

Number of nodes: 5

You can also try this code with Online C++ Compiler

Run Code

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-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-3 

Now we will print the obtained result from the function, i.e., we will print 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 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;
}

You can also try this code with Online C++ Compiler

Run Code

Output

Number of nodes: 5

You can also try this code with Online C++ Compiler

Run Code

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 courses, refer 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.