CPSC 220 Fall 2003
Homework 1: Binary Trees

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






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






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






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






For questions 5-8, give both an exact answer (e.g, (x2-1)/2) and an answer in big-O (e.g., O(x2)).
  1. What is the maximum number of nodes in a binary tree of height h?


  2. What is the minimum number of nodes in
    1. a binary tree of height h?


    2. a complete binary tree of height h?



  3. What is the maximum height of a binary tree with n nodes?


  4. What is the minimum height of a binary tree with n nodes?