The number of leaf nodes in a rooted tree of n nodes, with each node having 0…

Concept

In any rooted tree the edges can be counted in two independent ways, and the two counts must agree. Counted from below, every node except the root is reached by exactly one edge from its parent, so a tree on n nodes has exactly n − 1 edges. Counted from above, each node contributes one edge for every child it has, so the edge total is the sum of all the children-counts. Equating these two counts is the standard way to turn a branching rule into a node count.

Application

1. Split the nodes by role. Let I be the number of internal nodes (nodes that have children) and L the number of leaf nodes (nodes with no children). Every node is one or the other, so n = I + L.

2. Count the edges from the node total. A rooted tree on n nodes has n − 1 edges.

3. Count the same edges from the branching rule. Each node has 0 or 3 children, so each internal node contributes exactly 3 edges and each leaf contributes 0. The edge total is therefore 3I.

4. Equate the two counts of the same edge set: 3I = n − 1, so I = (n − 1)/3.

5. Substitute into n = I + L to isolate the leaves: L = n − I = n − (n − 1)/3.

6. Put the right-hand side over a common denominator: L = (3n − (n − 1))/3 = (3n − n + 1)/3 = (2n + 1)/3.

Cross-check

Rebuild the smallest such trees and count the leaves directly. Growing the tree means replacing one leaf by an internal node with three children, which adds 3 nodes and 2 leaves each time.

Contrast

The same edge-counting argument distinguishes the near-miss expressions:

• (n − 1)/2 is what the argument gives when each internal node has 2 children instead of 3, so it belongs to the binary case, not to this one.

• (n − 1)/3 stops at step 4 and reports I, the internal-node count, without the final subtraction from n.

• n/2 uses no branching information at all: it assumes leaves and internal nodes occur in equal numbers, which the 0-or-3 rule does not produce.

Result

The number of leaf nodes is (2n + 1)/3. Note also that 3I = n − 1 forces n − 1 to be a multiple of 3, so n is always of the form 3I + 1 for such a tree.