CIS 125

21 – Binary Trees

In exercises 1-3, draw a graph having the following properties, or explain why no such graph exists.

1. Full binary tree; four internal vertices, five terminal vertices.

2. Full binary tree; height=3; nine terminal vertices.

3. Full binary tree; height=4; nine terminal vertices.

In exercises 4-8, list the order in which the vertices are processed using preorder (pre-fix), inorder(in-fix) and postorder (post-fix) traversal.

4.

5.

6.

7.

8.