CSE 326 Summer 2003
Homework 4

Due Wed July 23, beginning of class

70 Points total.

1. (20 points)
a. Show the result of inserting 10,15,12,3,1,13, and 8 into an initially empty AVL tree.

b. Show the result of inserting 10,15,12,3,1,13, and 8 into an initially empty Splay tree.

c. Show the result of inserting 10,15,12,3,1,13, and 8 into an initially empty Leftist Heap.

d. Show the result of inserting 10,15,12,3,1,13, and 8 into an initially empty Skew Heap.

2. (10 points) We define 2 binary trees to be similar if they are either both empty or else they are both nonempty and have similar left and right subtrees. Give an algorithm to decide whether 2 binary trees are similar. What is the running time of your algorithm?

3. (10 points) Give an algorithm that takes a binary search tree as input along with 2 keys, x and y, with x <= y, and prints all keys z in the tree such that x <= z <= y. What is the running time of your algorithm?

4. (10 points) Given the root of a tree, suppose we want to verify that the tree is an AVL tree.

a. Give an algorithm to test whether the tree satisfies the search tree order property at every node. Your algorithm should run in O(n) time, where n is the number of nodes in the tree.

b. Assuming height information is stored at each node, give an algorithm to test whether this height information is correctly maintained and whether the balance property is satisfied at each node. This method should also run in O(n) time.

5. (18 points) Define a level order traversal of a binary tree to traverse each node on the top level of the tree (the root) from left to right, and then the second level from left to right, . .., and finally each node on the lowest level of the tree from left to right. For example, the level order traversal of the tree below is 9,14,4,11,8,15,2.  Define a reverse level order traversal of a binary tree to traverse each node on the lowest level of the tree from left to right, and then each node on the second lowest level of the tree from left to right, ..., and finally each node on the top level of the tree (the root) from left to right. For example, the reverse level order traversal of the tree below is 2,11,8,15,14,4,9.  Please note that a reverse level order traversal is not just an inverted level order traversal.

a. Given the root of a binary tree, give an algorithm to print out the level order traversal. (Hint: consider what you learned in Homework 3, part B!)

b. Given the root of a binary tree, give an algorithm to perform a reverse level order traversal of the tree. (Hint: try using a stack and queues in your algorithm)

6. (2 points) What did you enjoy about this assignment? What did you dislike? Could we have done anything better?