Fully Binary Tree

A binary tree is called a fully binary tree if each non-leaf node has two children. Suppose there are $n$ leaf nodes. Then the number of non-leaf nodes is $n - 1$. To see this, we remove a pair of leaves that shares the same parent repeatedly until there are 3 nodes left. Each time we remove such a pair of nodes, both the number of leaf nodes and the number of non-leaf nodes decreases by one. Therefore the difference between the number of leaf and non-leaf node remains. By induction we see that the difference is exactly one.