Week 10 Tutorial — Sample Solutions

  1. Pushing a char into a quack: 
    char bigA = 'A';
push((int)bigA, play); // cast the char to an int before pushing

    Popping a char from a quack: 
    char c;
c = (char)pop(play);   // cast the int to a char after popping

  2. The basic algorithm is:
    1. (]
      • the last popped char does not match ']': error

    2. ())
      • stack is empty when second ')' is read, so there are too few opening brackets: error

    3. (()
      • stack is not empty at the end, hence there are unmatched opening brackets: error

    1. Output using iterative freeing: 

      free node 1
free node 2
free node 3
free node 4

    2. A function to recursively free nodes, in forward direction: 

      void freeList(NodeT *cur) {
   if (cur != NULL) {
      NodeT *temp;
      temp = cur->next;
      printf("free node %d\n", cur->data);
      free(cur);
      freeList(temp);
   }
}

      the output will be: 
      free node 1
free node 2
free node 3
free node 4

      The above recursive function is an example of tail recursion:
      • the recursive call is made at the end of the function

    3. A function to recursively free nodes, in backward direction:

      void freeList(NodeT *cur) {
   if (cur != NULL) {
      freeList(cur->next);
      printf("free node %d\n", cur->data);
      free(cur);
   }
}

      the output will be: 
      free node 4
free node 3
free node 2
free node 1

      The above recursive function is an example of head recursion:
      • the recursive call is made before the current node is freed

    4. The essential difference between head and tail recursion is the placement of the recursive call relative to the 'action': 
      free(cur);
freeList('cur->next');
      traverses and frees in the forward direction, whereas the recursive call before the free: 
      freeList(cur->next);
free(cur);
      traverses and frees in the backward direction.

  4. Freeing a tree in postfix order is the only way to do it. 

    void freeTree(Tree t) {   // free all memory associated with the tree
   if (t != NULL) {
      freeTree(t->left);  // must free the children first
      freeTree(t->right);
      free(t);
   }
}

  5. In essence: