Count the number of leaf nodes in a Binary Tree

Given a binary tree, write a program to count the number of leaf nodes. A leaf node is a node that does not have any children (i.e., both left and right children are null or None).

Input/Output Examples

cpp
Example 1:
Input:
markdown
Copy code
     1
    / \
   2   3
  / \
 4   5

Output:
3
Explanation: The leaf nodes are 4, 5, and 3, so the total number of leaf nodes is 3.

Example 2:
Input:
markdown
Copy code
     1
    / \
   2   3
  /
 4

Output:
2
Explanation: The leaf nodes are 4 and 3, so the total number of leaf nodes is 2.

Approach to Count the Number of Leaf Nodes in a Binary Tree

  1. Recursive Approach:
    • Traverse the binary tree using a depth-first search (DFS).
    • For each node, check if both the left and right children are null (i.e., it’s a leaf node). If yes, increment the leaf count.
    • Recursively apply this process to both the left and right subtrees.
  2. Edge Case:
    • If the tree is empty (i.e., the root is null or None), return 0.

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

cpp
#include <iostream>
using namespace std;

// Definition of a binary tree node
struct TreeNode {
    int data;
    TreeNode* left;
    TreeNode* right;

    TreeNode(int val) : data(val), left(NULL), right(NULL) {}
};

// Function to count the number of leaf nodes
int countLeafNodes(TreeNode* root) {
    if (root == NULL) {
        return 0;
    }
    
    // If this node is a leaf node
    if (root->left == NULL && root->right == NULL) {
        return 1;
    }

    // Recursively count leaf nodes in the left and right subtrees
    return countLeafNodes(root->left) + countLeafNodes(root->right);
}

int main() {
    // Create a sample tree
    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);

    // Count and print the number of leaf nodes
    cout << "Number of leaf nodes: " << countLeafNodes(root) << endl;
    return 0;
}

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

java
// Definition of a binary tree node
class TreeNode {
    int data;
    TreeNode left, right;

    TreeNode(int val) {
        data = val;
        left = right = null;
    }
}

public class CountLeafNodes {

    // Function to count the number of leaf nodes
    public static int countLeafNodes(TreeNode root) {
        if (root == null) {
            return 0;
        }

        // If this node is a leaf node
        if (root.left == null && root.right == null) {
            return 1;
        }

        // Recursively count leaf nodes in the left and right subtrees
        return countLeafNodes(root.left) + countLeafNodes(root.right);
    }

    public static void main(String[] args) {
        // Create a sample tree
        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);

        // Count and print the number of leaf nodes
        System.out.println("Number of leaf nodes: " + countLeafNodes(root));
    }
}

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

python
# Definition of a binary tree node
class TreeNode:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

# Function to count the number of leaf nodes
def count_leaf_nodes(root):
    if root is None:
        return 0

    # If this node is a leaf node
    if root.left is None and root.right is None:
        return 1

    # Recursively count leaf nodes in the left and right subtrees
    return count_leaf_nodes(root.left) + count_leaf_nodes(root.right)

# Example usage
if __name__ == "__main__":
    # Create a sample tree
    root = TreeNode(1)
    root.left = TreeNode(2)
    root.right = TreeNode(3)
    root.left.left = TreeNode(4)
    root.left.right = TreeNode(5)

    # Count and print the number of leaf nodes
    print("Number of leaf nodes:", count_leaf_nodes(root))
  • Time Complexity: O(n), where n is the number of nodes in the binary tree. Each node is visited once to check whether it is a leaf node.
  • Space Complexity: O(h), where h is the height of the tree. This space is required for the recursive call stack. In the worst case (for a skewed tree), the space complexity is O(n).

DSA

4400

771

Related Articles