CPSC 220 Fall 2006
HW 7: Intro to Binary Trees

Read sections 12.1-12.3 in L&C.
  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?