Introduction to Algorithms
Week 9: Exercises

1. Recursive Ones and Zeros

Write a recursive function printBinary(n) that prints out the binary representation of n.

2. Random Tree

Write a function randomTree(h) that builds a complete binary tree of height h. Every value in the tree should be a random integer in the range 0 .. 999.

3. Complete Tree

Write a function completeTree(h) that builds a complete binary tree of height h. Every node's value should be that node's depth.

4. Mirror Image

Write a function mirror(t) that flips a tree from left to right so that it looks like a mirror image of the original tree.

5. Tree Compare

Write a function equal(t, u) that takes two Node objects representing the roots of two binary trees. The function should return True if the binary trees are identical, i.e. they have the same structure and the same values in corresponding nodes.

6. Tree Walk

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

7. Ancestor Check

Write a function isAncestor(p, q) that takes pointers to two nodes p and q in a binary tree and returns true if p is an ancestor of q. (The tree is not necessarily a binary search tree.)

8. Array to Tree

Write a function that takes an array containing a sorted list of integers and returns a binary search tree containing all the values in the array. The tree should be as balanced as possible, i.e. it should have the minimum possible height.

9. Tree Check

Write a method that takes a binary tree and returns true if the tree satisfies the ordering requirements of a binary search tree.

10. Biggest Gap

Write a function that returns the greatest difference between any two consecutive values in a binary search tree.

11. Tree Successor

Write a method which, given a binary search tree of non-negative integers and an integer i, returns the next highest value in the tree, i.e. the smallest value in the tree that is greater than i. Return -1 if there are no values greater than i. 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 method that 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(h + n), where h is the tree height and n is the number of integers in the range.

13. Hash Chain Lengths

Write a program that reads an integer N and simulates inserting (100 · N) values into a hash table with N buckets using separate chaining, assuming uniform hashing. The program should print the lengths of the longest and shortest chains.

14. Empty Buckets

Suppose that we insert N values into a hash table with N buckets. What fraction of the buckets do we expect will be empty? Assume that N is a large number.

15. Counting Sundays

Solve Project Euler's problem 19.