Try It Now
Work these exercises to see how well you understand this material.
- Solution 1:
Basis: A binary tree consisting of a single vertex, which is a leaf, satisfies the equation leaves = internal vertices + 1
Induction: Assume that for some k ≥ 1, all full binary trees with k or fewer vertices have one more leaf than internal vertices. Now consider any full binary tree with k + 1 vertices. Let TA and TB be the left and right subtrees of the tree which, by the definition of a full binary tree, must both be full. If iA and iB are the numbers of internal vertices in TA and TB, and jA and jB are the numbers of leaves, then jA = iA+ 1 and jB = iB+ 1.
Therefore, in the whole tree, the number of leaves = jA + jB
= (iA + 1) + (iB + 1)
= (iA + iB + 1) + 1
= (number of internal vertices) + 1
- Solution 2:
Imagine building a full binary tree starting with a single vertex. By continuing to add leaves in pairs so that the tree stays full, we can build any full binary tree. Our starting tree satisfies the condition that the number of leaves is one more than the number of internal vertices. By adding a pair of leaves to a full binary tree, an old leaf becomes an internal vertex, increasing the number of internal vertices by one. Although we lose a leaf, the two added leaves create a net increase of one leaf. Therefore, the desired equality is maintained.
- Solution 1: