Binary Search Tree Assignment

Base Assignment:

1. write contains (6pts)
2. write traverseInorder (6pts)
3. write randomizedSort and tester (4pts for sort, 2 pts for tester)

Areas to explore:

WRITE DELETE

You will want to read the wikipedia page on delete, and consider three cases:

• leaf delete (2 pts)
• single parent delete (2 pts)
• dual parent delete (2 pts)

The last one is trickier, do it one at a time.

MAKE IT A SELF BALANCING AVL TREE

you will need to change insert (6pts) and delete (5pts). Read about this on wikipedia, and consider making a pointer to each relevant node before you re-organize.

DRAW IT

Use lattelib to draw the BST. You can make class function called BTree consider making an interface to add/remove from the bst. (Up to 10 points)

IMPROVE THE TESTER

Add some edge cases or improvements to the contains and traverse testers