Write a procedure that bubble sorts an array of integers, stopping immediately when it sees that all array elements are in order.
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.)
Modify the merge sort implementation we saw in lecture to be non-recursive.
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.
Write a procedure that prints out all values in a binary search tree in increasinng order.
Write a function that computes the sum of all values in a binary tree of integers.
Write a function that returns the height of a binary tree.
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.
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.
Modify the binary tree implementation from the lecture so that each node includes a link to its parent node.
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.
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.
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