Number of leaf nodes in full binary tree

Question

Problem Find the number of leaf nodes in a full binary tree with n nodes.

I wrote a recursive program for the above problem, traversing the tree and increasing the count of leaf nodes whenever I reach a node which has no children. But since the tree is a full binary tree I think that it will make the problem easier but I can't figure it out how. Can it be reduced in a compact form (something like a formula).

Answer 1

The number of leaf nodes in a full binary tree with n nodes is equal to (n+1)/2.

Refrence to the above formula.

Answer 2

You start with 1 leaf node and each branching step creates 2 new leaf nodes, and one leaf node turns into an internal node (for a net of +1 leaf in the tree). So the tree has 2b+1 nodes, b internal nodes, and b+1 leaves, where b is the number of branchings.

n = 2b+1

b = (n-1)/2