### CPSC 220 Fall 2006HW 7: Intro to Binary Trees

1. Give the preorder, inorder, postorder and levelorder traversals for the tree below.
```           H
/ \
/   \
B     K
/ \   /
F   E  D
/      / \
J      G   A
/ \          \
L   C          I

```
2. Draw a binary tree whose preorder traversal is A B C D E F G H I.

3. Draw a binary tree whose inorder traversal is A B C D E F G H I.

4. Draw a binary tree whose postorder traversal is A B C D E F G H I.

5. Draw a binary tree whose levelorder traversal is A B C D E F G H I.

1. Draw the most filled-in binary tree with height 2 you can (that is, the tree with the most nodes). Show the picture. How many nodes does the tree have?
2. Draw the most filled-in binary tree with height 3 you can (that is, the tree with the most nodes). Show the picture. How many nodes does the tree have?
3. What is the maximum number of nodes in a binary tree of height h? (Look for a pattern in (a) and (b) and convince yourself that it holds for all heights.)

1. Draw the least filled-in binary tree with height 2 you can (that is, the tree with the fewest nodes). Show the picture. How many nodes does the tree have?
2. Draw the least filled-in binary tree with height 3 you can (that is, the tree with the fewest nodes). Show the picture. How many nodes does the tree have?
3. What is the minimum number of nodes in a binary tree of height h?

1. Draw the least filled-in complete binary tree of height 2 you can (that is, the tree with the fewest nodes). Show the picture. How many nodes does the tree have?
2. Draw the least filled-in complete binary tree of height 3 you can (that is, the tree with the fewest nodes). Show the picture. How many nodes does the tree have?
3. What is the minimum number of nodes in a complete binary tree of height h?

1. Draw the tallest binary tree you can using 2 nodes. Show the tree. What is its height?
2. Draw the tallest binary tree you can using 3 nodes. Show the tree. What is its height?
3. What is the maximum height of a binary tree with n nodes?