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

Introduction

Binary trees are a fundamental data structure in computer science, used to represent hierarchical relationships. Each node in a binary tree has at most two children, referred to as the left child and the right child. One of the key properties of a binary tree is the distinction between internal nodes (nodes with at least one child) and leaf nodes (nodes with no children). Counting the number of leaf nodes in a binary tree is a common problem, and this article will guide you through implementing a C++ program to achieve this.

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.
Leaf Node: A node with no children.
Tree Traversal: The process of visiting all nodes in a tree in a specific order (e.g., in-order, pre-order, post-order).

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

Implementing the Binary Tree

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

Define a class for the binary tree node.
Implement a function to count leaf nodes.
Create a binary tree and use the function to count its leaf nodes.

Pseudocode for Counting Leaf Nodes

If the current node is null, return 0.
If the current node is a leaf node (no left and right children), return 1.
Recursively count the leaf nodes in the left and right subtrees and return their sum.

Example

Example 1: Simple Binary Tree

Binary Tree Representation

Consider a simple binary tree:

C++

In this tree, the leaf nodes are 4, 5, and 3.

C++ Program

C++

#include <iostream>

using namespace std;

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

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

int countLeafNodes(Node* root) {
    if (root == nullptr) {
        return 0;
    }
    if (root->left == nullptr && root->right == nullptr) {
        return 1;
    }
    return countLeafNodes(root->left) + countLeafNodes(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 leaf nodes: " << countLeafNodes(root) << endl;

    return 0;
}

Output

C++

Number of leaf nodes: 3

Additional Examples

Example 2: Larger Binary Tree

Binary Tree Representation

Consider a larger binary tree:

C++

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

In this tree, the leaf nodes are 4, 7, 8, and 6.

C++ Program

C++

#include <iostream>

using namespace std;

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

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

int countLeafNodes(Node* root) {
    if (root == nullptr) {
        return 0;
    }
    if (root->left == nullptr && root->right == nullptr) {
        return 1;
    }
    return countLeafNodes(root->left) + countLeafNodes(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 leaf nodes: " << countLeafNodes(root) << endl;

    return 0;
}

Output

C++

Number of leaf nodes: 4

Example 3: Binary Tree with Single Node

Binary Tree Representation

Consider a binary tree with a single node:

C++

In this tree, the single node itself is the leaf node.

C++ Program

C++

#include <iostream>

using namespace std;

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

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

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

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

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

    return 0;
}

Output

C++

Number of leaf nodes: 1

Conclusion

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