The number of leaf nodes in a full 4-ary rooted tree of n nodes is

Explanation

In a full k-ary tree, every internal node has exactly k children, so if there are I internal nodes and L leaf nodes, the total number of edges equals kI; since any tree with n nodes has exactly n − 1 edges, kI = n − 1, giving I = (n − 1)/k. The number of leaves is then L = n − I = n − (n − 1)/k = ((k − 1)n + 1)/k. Substituting k = 4 gives L = (3n + 1)/4. So the number of leaf nodes is (3n + 1)/4.