C++ Program to Count the Number of Nodes in a Binary Tree

A binary tree is a hierarchical data structure in which each node has at most two children, referred to as the left child and the right child. Counting the number of nodes in a binary tree is a common operation used in various applications, such as evaluating the size of the tree, balancing the tree, and more. This article will guide you through the implementation of a C++ program to count the number of nodes in a binary tree, providing detailed explanations and examples to enhance your understanding.

Prerequisites

Before diving into the implementation, it’s important to understand the following concepts:

• Binary Tree: A tree data structure in which each node has at most two children.
• Tree Traversal: The process of visiting all nodes in a tree in a specific order (e.g., in-order, pre-order, post-order).
• Recursion: A method where the solution to a problem depends on solutions to smaller instances of the same problem.

Familiarity with C++ programming, including classes and recursion, will be beneficial.

Implementing the Binary Tree

To count the number of nodes in a binary tree, we will:

1. Define a class for the binary tree node.
2. Implement a function to count the nodes recursively.
3. Create a binary tree and use the function to count its nodes.

Pseudocode for Counting Nodes

1. If the current node is null, return 0.
2. Recursively count the nodes in the left subtree.
3. Recursively count the nodes in the right subtree.
4. Return the sum of the nodes in the left subtree, right subtree, and the current node (1).

Example

Example 1: Simple Binary Tree

Binary Tree Representation

Consider a simple binary tree:

      1
     / \
    2   3
   / \
  4   5

In this tree, there are 5 nodes.

C++ Program

#include <iostream>

using namespace std;

class Node {
public:
    int data;
    Node* left;
    Node* right;

    Node(int val) {
        data = val;
        left = nullptr;
        right = nullptr;
    }
};

int countNodes(Node* root) {
    if (root == nullptr) {
        return 0;
    }
    return 1 + countNodes(root->left) + countNodes(root->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);

    cout << "Number of nodes: " << countNodes(root) << endl;

    return 0;
}

Output

Number of nodes: 5

Additional Examples

Example 2: Larger Binary Tree

Binary Tree Representation

Consider a larger binary tree:

         1
       /   \
      2     3
     / \     \
    4   5     6
       / \
      7   8

In this tree, there are 8 nodes.

C++ Program

#include <iostream>

using namespace std;

class Node {
public:
    int data;
    Node* left;
    Node* right;

    Node(int val) {
        data = val;
        left = nullptr;
        right = nullptr;
    }
};

int countNodes(Node* root) {
    if (root == nullptr) {
        return 0;
    }
    return 1 + countNodes(root->left) + countNodes(root->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);
    root->right->right = new Node(6);
    root->left->right->left = new Node(7);
    root->left->right->right = new Node(8);

    cout << "Number of nodes: " << countNodes(root) << endl;

    return 0;
}

Output

Number of nodes: 8

Example 3: Binary Tree with Single Node

Binary Tree Representation

Consider a binary tree with a single node:

  1

In this tree, there is 1 node.

C++ Program

#include <iostream>

using namespace std;

class Node {
public:
    int data;
    Node* left;
    Node* right;

    Node(int val) {
        data = val;
        left = nullptr;
        right = nullptr;
    }
};

int countNodes(Node* root) {
    if (root == nullptr) {
        return 0;
    }
    return 1 + countNodes(root->left) + countNodes(root->right);
}

int main() {
    Node* root = new Node(1);

    cout << "Number of nodes: " << countNodes(root) << endl;

    return 0;
}

Output

Number of nodes: 1

Conclusion

Counting the number of nodes in a binary tree is a common problem that can be efficiently solved using a recursive approach. By understanding the structure of a binary tree and implementing the counting function, you can easily determine the total number of nodes in the tree.