### 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.

### 13. 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.

### 14. 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.

### 15. Drawing a Tree

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

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