C++ Coding Test Course, Counting the Number of Leaf Nodes

This article will explain in detail how to count the number of leaf nodes using the C++ programming language. It is structured to be easily understandable from start to finish, including the process of solving the algorithm problem and the code.

Problem Description

A leaf node refers to a node that has no child nodes. Write a program to count the number of leaf nodes in a given binary tree. The input for this problem will be the root node of the binary tree.

Input format:

  • The root node of the binary tree (the root node may be nullptr.)

Output format:

  • The number of leaf nodes

Algorithm Approach

To solve this problem, we will traverse the binary tree recursively. Each time we visit a node, we check if it is a leaf node. A leaf node has no child nodes, so we simply need to check if both the left and right child nodes are nullptr.

Specific Algorithm:

  1. If the root node is nullptr, return 0.
  2. If the node is a leaf node, return 1.
  3. Recursively traverse the left and right subtrees, summing and returning the results.

C++ Code Implementation

Now let’s take a look at the code that implements the above algorithm in C++.


#include <iostream>

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

int countLeafNodes(TreeNode* root) {
    // 1. If the root is nullptr
    if (root == nullptr) {
        return 0;
    }
    
    // 2. If it is a leaf node
    if (root->left == nullptr && root->right == nullptr) {
        return 1;
    }
    
    // 3. Explore the left and right subtrees
    return countLeafNodes(root->left) + countLeafNodes(root->right);
}

int main() {
    // Create a binary tree for testing
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    root->left->right = new TreeNode(5);
    
    // Print the number of leaf nodes
    int leafCount = countLeafNodes(root);
    std::cout << "Number of leaf nodes: " << leafCount << std::endl;
    
    // Free allocated memory
    delete root->left->left;
    delete root->left->right;
    delete root->left;
    delete root->right;
    delete root;

    return 0;
}

Code Explanation

The code above implements the countLeafNodes function, which takes the root node of a binary tree and returns the number of leaf nodes.

Struct Declaration:

The TreeNode struct represents each node in the binary tree. Each node has an integer value (val) and pointers to the left child (left) and right child (right).

Counting Leaf Nodes:

The countLeafNodes function first checks if the root is nullptr. If nullptr, it returns 0, and if it’s a leaf node, it returns 1. Otherwise, it recursively calls the left and right subtrees to count and sum the number of leaf nodes.

Main Function:

The main function creates a binary tree for testing purposes and prints the number of leaf nodes corresponding to it. Finally, it is important to free the allocated memory.

Testing and Results

Executing this code will yield the following result:

Number of leaf nodes: 3

In the above binary tree, the leaf nodes are nodes 4, 5, and 3, resulting in a total of 3 leaf nodes.

Conclusion

In this article, we explained how to count the number of leaf nodes in a binary tree using C++. Through examples of understanding and implementing algorithms, we can learn the basic recursive calls and struct usage in C++. To solve algorithm problems, it is important to break down the problem and approach it step by step. We hope you continue to practice various problems to build your algorithm skills.

References