HW 8: Binary Search Trees

- Consider the values below:
14 20 38 6 12 30 17 10 33

- Show the BST you get from inserting these values in the order given.
- Is this tree unique? That is, is this the only correct answer to (a)? If not, give another correct answer.
- Give preorder, inorder, postorder, and level order traversals of this tree.

- Now...
- Construct a maximum height BST containing these same values.
- Is this tree unique? That is, is this the only correct answer to (a)? If not, give another correct answer.
- Show the order in which the values would be inserted to create this tree.
- 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..
- Give preorder, inorder, postorder, and level order traversals of this tree.

- Now...
- Construct a minimum height BST containing these same values.
- Is this tree unique? That is, is this the only correct answer to (a)?
- Show the order in which the values would be inserted to create this tree.
- 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.
- Give preorder, inorder, postorder, and level order traversals of this tree.

- 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).
- How many comparisons are needed to insert the first element?
- How many comparisons are needed to insert the second element?
- How many comparisons are needed to insert the third element?
- In general, how many comparisons are needed to insert the i
^{th}element? - If N elements are inserted in all, how many comparisons are needed to build the entire tree? CAREFULLY JUSTIFY YOUR ANSWER.

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