Week 04 Tutorial Notes

Group Question

1. Starting from an intially empty tree:
   1. Insert the values into the tree in this order: [10 11 6 4 5 8 7 9 1]
   2. What is the height of the resulting tree?
   3. What is the post-order traversal of this tree?
   • Draw a trace around the tree, similar to what your tutor demonstrated.
   4. What is a Post-Order traversal useful for?
   • In-Order: Prints the values in ascending order.
   • Pre-order: Copies the shape of the tree.
   5. Write down the pseudocode implementation for Post-Order.
   • Hint: It is 4-5 lines of C code.
   6. What line needs to change in your implementation to make it print an In-Order traversal instead?
   • Hint: Only 1 line needs modified and shifted within the function.


2. Your task is to draw the solution for this problem:

   int bstSumEvens(struct node *t);
   

   Redraw the diagram to answer the following questions:

   

   
   
   

   1. What should the function return when given the whole tree?
   2. What is the base case?
   • Circle one case on your diagram.
   • Give the answer for this base case.
   3. Starting at node 4:
   • Draw a Triangle around the Left subtree and lable L.
   • Draw a Triangle around the Right subtree and lable R.
   • What would the function return when it recurses on L?
   • What would the function return when it recurses on R?
   4. How do we combine the recursive steps for a full solution?
   5. Write out the pseudocode implementation.


3. Your task is to draw the solution for this problem:

   int bstHeight(struct node *t);
   

   Redraw the diagram to answer the following questions:

   

   
   
   

   1. What should the function return when given the whole tree?
   2. What is the base case?
   • Circle one case on your diagram.
   • Give the answer for this base case.
   3. Starting at node 4:
   • Draw a Triangle around the Left subtree and lable L.
   • Draw a Triangle around the Right subtree and lable R.
   • What would the function return when it recurses on L?
   • What would the function return when it recurses on R?
   4. How do we combine the recursive steps for a full solution?
   5. Write out the pseudocode implementation.




Group Work Answers:

Click each section to reveal.

Part 1:

1. Look at part c.
2. The height of the tree is 3.


3. 


4. Post-Order is useful for deleting the tree because it starts at the bottom most values first, and works it's way up the tree.


5. 


6. To change the above code into an In-Order Traversal change free(tree)
to printf(tree->value); and place it between the left and right recursive calls.

Part 2:

1. bstSumEvens() = 22 for the full tree.
2. Base Case is when the node is NULL. The answer to bstSumEvens() at this case is 0.


3. 


4. L + R + (the value of the node if it is even).



5. int bstSumEvens(struct node *t) {
       // BASE CASE: When tree is null return 0
       // L = bstSumEvens(tree->right);
       // R = bstSumEvens(tree->right);
       // if (t is odd) return L + R
       // else return L + R + t->value
   }
   

Part 3:

1. bstHeight() = 4 for the full tree.
2. Base Case is when the node is NULL.

   The answer to bstHeight() at this case is -1. Because a single node has height 0. We need a way to tell these two different cases apart.

   Also for a tree containing only one node, both left and right children are NULL, which gives height = max(-1,-1) + 1 = 0.



3. 


4. Max(L + R) + 1.



5. int bstHeight(struct node *t) {
       // BASE CASE
       if (t == NULL) return -1;
       // RECURSIVE STEP
       int lheight = bstHeight(t->left);
       int rheight = bstHeight(t->right);
       int max = (lheight > rheight) ? lheight : rheight;
       return max + 1;
   }
   




Bonus Group Question:

4. Given the head of a linked list can you find the midpoint by only using recursion?

   struct node findMid(struct node *curr);
   

   Examples:

   • [1 2 3 4 5 6] - midpoint is 4.
   • [1 2 3 4 5] - midpoint is 3.
   Write pseudocode for it.