Count Nodes

Counting Nodes

To count how many nodes are in a tree, use the same recursive pattern:

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

For the 7-node tree: 1 + count(left subtree of 3 nodes) + count(right subtree of 3 nodes) = 1 + 3 + 3 = 7.

Why This Works

Each recursive call counts a subtree. The base case returns 0 for empty subtrees. Each non-null node contributes exactly 1 to the total.

This is essentially the same structure as tree_sum — instead of summing values, you sum 1 per node.

Your Task

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