CPSC 220 Fall 2006
HW 8: Binary Search Trees

  1. Consider the values below: 
    14  20  38  6  12  30  17  10 33
    1. Show the BST you get from inserting these values in the order given.
    2. Is this tree unique? That is, is this the only correct answer to (a)? If not, give another correct answer.
    3. Give preorder, inorder, postorder, and level order traversals of this tree.

  2. Now...
    1. Construct a maximum height BST containing these same values.
    2. Is this tree unique? That is, is this the only correct answer to (a)? If not, give another correct answer.
    3. Show the order in which the values would be inserted to create this tree.
    4. Is this order unique? That is, for your tree in (a), is this the only correct answer to (c)? If not, give another correct answer..
    5. Give preorder, inorder, postorder, and level order traversals of this tree.

  3. Now...
    1. Construct a minimum height BST containing these same values.
    2. Is this tree unique? That is, is this the only correct answer to (a)?
    3. Show the order in which the values would be inserted to create this tree.
    4. Is this order unique? That is, for your tree in (a), is this the only correct answer to (c)? If not, give another correct answer.
    5. Give preorder, inorder, postorder, and level order traversals of this tree.

  4. Think about your maximum height BST in (2a) above and how it can be constructed by inserting elements in the order you give in (2c).
    1. How many comparisons are needed to insert the first element?
    2. How many comparisons are needed to insert the second element?
    3. How many comparisons are needed to insert the third element?
    4. In general, how many comparisons are needed to insert the ith element?
    5. If N elements are inserted in all, how many comparisons are needed to build the entire tree? CAREFULLY JUSTIFY YOUR ANSWER.

  5. Look at the traversals for your trees. Look for an interesting pattern and complete the sentence below: 
    A/An _______________ traversal of a BST always  _______________________________________.