In-lab 3

1.	How many nodes does a full 5-ary tree with 100 internal nodes have?_________

2.	How many leaves does a full 3-ary tree with 100 nodes have?_________
3.	What is the height of the shortest binary tree that contains 21 nodes?_________

4.	Suppose 1000 people enter a chess tournament.  Use a tree model of the tournament to determine how many games must be played to determine a champion, if a player is eliminated after one loss and games are played until only one entrant has not lost.  (Assume there are no ties.)

5.	Either draw a full m-ary tree with 76 leaves and height 3 where m is a positive integer or show that no such tree exists.

6.	Build a binary search tree for the words banana, peach, apple, pear, coconut, mango, and papaya using alphabetical order.

7.	How many comparisons are needed to locate or to add each of the following words in the search tree you drew above.
a.	pear ________
b.	banana ________
c.	kumquat ________
d.	orange ________

8.	Do a preorder, inorder and postorder traversal of the tree.

9.	Show what the tree will look like if the node containing banana is deleted.

10.	Do a preorder traversal of the tree at right.  
	You can assume you output the node name 
	when you visit the node.

11.	Do an inorder traversal of the tree at right.

12.	Do a postorder traveral of the tree at right.

13.	Show what the BST at right  will look like if the node 5  is deleted.  (Redraw the tree).

14. 	Draw a maximum heap with 50 at the root and 10 nodes  		

15.  Draw a minimum heap with 50 at the root and 10 nodes
           		        	       .

16.	Draw two expression trees, one for the expression a + b * c and (a + b) * c

17.	Pseudo code for adding a node to a BST was given in class and can be found in the notes.  Modify the code so that it searches for a key instead of adding the key.  The method should return a reference variable (pointer) to the node where the key is found, or null if it is not found.  It takes as arguments a reference variable pointing to the root of the tree to be searched, and the key to be searched for. 

Use the following tree to walk through your code so you are sure it is correct.  Add whatever other reference variables or arrows that you need.  When walking through your code, you should test for both values that are found and those that are not.