9.11 Show that in any complete binary tree t, at least half of the elements are leaves. Hint: if t is empty, there are no elements, so the claim is vacuously true. If the leaf at the highest index is a right child, then t is a two-tree, and the claim follows from part 3 of the Binary Tree Theorem. Otherwise, t was formed by adding a left child to the complete two-tree with n(t ) − 1 elements. | |
| View Solution | |
| << Back | Next >> |