CSCE 3110 Data Structures
Assigment 3
Total: 80 points
Issued: 03/09/2006
Due: 03/23/2006
................................


1. (10 points) Consider a tree storing 100,000 items. What is the worst-case
height of T in the following cases:
       a. T is an AVL tree.
       b. T is a binary search tree.
Justify your answers.

2. (30 points) Write a program that implements a function SwapTree() that 
takes a binary tree and swaps the left and the right children of every node. 
What is the running time of your algorithm? Save your program as swapTree.cpp

3. (25 points) Write a program that takes as input a binary tree T, and 
outputs the tree that results after removing all leaves from T. Save your
program as removeLeaves.cpp

4. (15 points) Write the pseudo-code for a non-recursive function to 
insert one node into an AVL tree.


Submission instructions:  
   - write a README file including the answers to problems 1 and 4, and a 
     detailed note about the functionality of each of the above programs, 
     and complete instructions on how to run them.
   - make sure you include your name in each program and in the README file.
   - make sure all your programs are fully commented, and compile and run 
     correctly on the CSP machines.
   - submit your assignment by the due date using the 'project' program.
     class code is 3110s002, project HW3.