## Try It Now

Work these exercises to see how well you understand this material.

### Solutions

$\begin{matrix} & \mathrm{Preorder} & \mathrm{Inorder} & \mathrm{Postorder} \\ (a) & \cdot a + bc & a \cdot b+c & abc + \cdot\\ (b) & + \cdot abc & a\cdot b+c & ab \cdot c+\\ (c) & + \cdot ab \cdot ac & a \cdot b + a \cdot c & ab \cdot ac \cdot + \end{matrix}$

1. 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 Tand Tbe the left and right subtrees of the tree which, by the definition of a full binary tree, must both be full. If iand iare the numbers of internal vertices in Tand TB, and jand jare the numbers of leaves, then j= iA+ 1 and j= iB+ 1.

Therefore, in the whole tree, the number of leaves = j+ jB
= (i+ 1) + (i+ 1)
= (i+ i+ 1) + 1
= (number of internal vertices) + 1

2. 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.