# Try It Now

 Site: Saylor Academy Course: CS202: Discrete Structures Book: Try It Now
 Printed by: Guest user Date: Friday, July 12, 2024, 11:23 AM

## Description

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

## Exercises

1. Draw the expression trees for the following expressions:
1. a(b + c)
2. ab + c
3. ab + ac
4. bb 4ac
5. ((a3x + a2)x + a1)x + a0

2. Write out the preorder, inorder, and postorder traversals of the trees in Exercise 1 above.

1. Draw a binary tree with seven vertices and only one leaf.
2. Draw a binary tree with seven vertices and as many leaves as possible.

3. Prove that if T is a full binary tree, then the number of leaves of T is one more than the number of internal vertices (non-leaves).

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