Count Leaves

Counting Leaf Nodes

A leaf node is a node with no children — both left and right are NULL.

        4
       / \
      2   6
     / \ / \
    1  3 5  7   ← these 4 are leaves

Implementation

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

Three cases:

1. NULL — empty subtree, contributes 0 leaves.
2. Leaf — no children, contributes 1.
3. Internal node — has at least one child, leaves are in the subtrees.

Your Task

Implement int count_leaves(struct Node *root) that returns the number of leaf nodes in the tree.