Homework #4

Due : May 17 , 2004

The following problems are from R.Johnsonbaugh's Discrete Mathematics :
1. #2 #3 #5 #6 section 10.3 page 471-472
2. #16 #17 section 10.3 page 472
3. #26 ,#27 section 10.3 page 472
The following problems are from Weiss' Text :
1. #4.8 page 146 : Give the prefix, infix and postfix expressions corresponding to the tree in Figure 4.65.
2. #4.9 :
  1. Show the result of inserting 3,1,4,6,9,2,5,7 into an initially empty binary search tree.
  2. Show the result of deleting the root.
3. #4.18 (b) only : What is the minimum number of nodes in an AVL tree of height h = 15?
4. #4.19 page 147 : Show the result of inserting 2,1,4,5,9,3,6,7 into an initially empty AVL tree.
5. #4.31 page 148 : Write efficient methods that takes only a reference to the root of a bianary tree,T, and compute :
  1. The number of nodes in T
  2. The number of leaves in T
  3. The number of full nodes in T.
  What is the running time of your routines?