Write a function tree_height(t) that returns the height of a binary 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.
Write a function that prints out all values in a binary search tree in order, separated by spaces.
Write a function that takes a binary tree and constructs a second tree that contains all the value from the first tree and is as balanced as possible.
Write a function that takes an integer N and inserts N random values in the range from 0 .. N – 1 into a binary search tree. Let r be the ratio of the tree's height to the minimum possible height of any tree that holds N values. The function should compute and return r.
Write a method that takes a binary tree and returns true if the tree satisfies the ordering requirements of a binary search tree.
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.
Write a function that returns the greatest difference between any two consecutive values in a binary search tree.
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.
Write a function that computes the sum of all values in a binary tree without using recursion.
Write a program that reads words from a file whose name is given on the command line. For each unique word in the file, the program should compute a hash value in the range 0..63 using the string hashing function we saw in the lecture. Then it should print a histogram: for each hash value, display a number of asterisks showing how many different words hashed to that value.
Modify the string hashing function from the lecture to run in constant space.