Week 7: Optional Exercises

1. Adaptive Bubble Sort

Write a procedure that bubble sorts an array of integers, stopping immediately when it sees that all array elements are in order.

2. Recursive Insertion

In the lecture we saw an iterative implementation of insertion sort. Rewrite insertion sort recursively. (You may keep the inner while loop or, if you wish, use more recursion so that loop is eliminated as well.)

3. Non-Recursive Merge Sort

Modify the merge sort implementation we saw in lecture to be non-recursive.

4. Dictionary

Write a unit that implements the dictionary interface we saw in the lecture. You can use an array, linked list or tree as you like.

5. Tree Walk

Write a procedure that prints out all values in a binary search tree in increasinng order.

6. Tree Sum

Write a function that computes the sum of all values in a binary tree of integers.

7. Tree Height

Write a function that returns the height of a binary tree.

8. Order Check

Write a function that returns true if a the values in an arbitrary binary tree of integers satisfy the ordering requirements of a binary search tree.

9. Biggest Gap

Write a function that returns the greatest difference between any two consecutive values in a binary search tree. If x < y, then the values x and y are consecutive if there is no value z in the tree such that x < z < y.

10. Tree with Parents

Modify the binary tree implementation from the lecture so that each node includes a link to its parent node.

11. Tree Successor

Write a function which, given a binary search tree of non-negative integers and an integer i, returns the next highest value in the tree, or -1 if i is the highest value. Assume that all integers in the tree are unique. The value i may or may not be present in the tree. Your function should run in time O(h), where h is the height of the tree.

12. Tree Range

Write a function which determines how many values v in a binary search tree of unique integers fall in the range a ≤ v ≤ b, where a and b are function parameters. The function should run in time O(n), where n is the number of integers in the range.

13. Drawing a Tree

Write a procedure drawTree that can print out a binary tree in a way that looks more or less like this:

   /  \
  6    17
 / \   / \
2   4 15  20