HW2

Assignment Due 19 May

NOTE: Partial credit is easier to give if your answers are verbose. Show lots of math and don't be afraid of using sentences.

1. Please write an iterative version of add for a bst. (Hint: use a trav pointer like we did with linked lists)
2. Please write an interative version of toString for a bst. (Hint: You will need a stack to keep track of the parent nodes)
3. Its a race!!! I want to know whose the fastest. Generate one million random integers between 1 and ten thousand. Store them into a bst ( the old fashioned sort ). Do this ten times. Then find the average. Then find the average for our iterative bst, avl tree, and java's built in Binary search tree. In your email, list the averages and your conclusions. Who is the fastest at adding. Also turn in your testing program.
4. Exercise 5.18. I would create two very small text files that contain 10 words each to test this sucker.