ANSWERS TO EXERCISES ON BINARY TREES



 1. Inorder:      - C - B - D - A - E - F -
    Postorder:    - - C - - D B - - - F E A

 2.  
                      left              middle                right
    preorder      D B A C F E G        C B A D E        E C B A D H F G I
    inorder       A B C D E F G        A B C D E        A B C D E F G H I
    postorder     A C B E G F D        A B E D C        A B D C G F I H E
    level-order   D B F A C E G        C B D A E        E C H B D F I A G


 3. (a)    int treecount(link x) {
              if (x == NULL)
                 return 0;
              else
                 return 1 + treecount(x->l) + treecount(x->r);
           }

    (b)    int treesum(link x) {
              if (x == NULL)
                 return 0;
              else
                 return x->key + treesum(x->l) + treesum(x->r);
           }

    (c)    int treemax(link x) {
              if (x == NULL)
                 return -1;
              else
                 return max3(x->key, treemax(x->left), treemax(x->right));
           }

          The max3 function is borrowed from the Functions exercises.

 4.        void treeless(link x, int val) {
              if (x == NULL)                      /* 0 */
                 return;
              if (x->key < val)                   /* 1 */
                 printf("%d\n", x->key);         
              treeless(x->l, val);                /* 2 */
              treeless(x->r, val);                /* 3 */
           }

    Note that statements 1, 2, and 3 can appear in any order.
    The base case (statement 0) must be first.


 5. (a)    int treeheight(link x) {
              if (x == NULL)
                 return 0;
              else
                 return 1 + max(treeheight(x->l), treeheight(x->r));
           }

           We use the max function from the Functions exercises.

    (b)    int treecost(link x) {
              if (x == NULL)
                 return 0;
              else
                 return x->key + max(treecost(x->l), treecost(x->r));
           }

 6. Apparently, the height needs to be computed, at least until some
    unbalanced node is found.  So this routine returns the height if
    the tree is balanced, and -1 if it is not balanced.
        
        int treebalanced(link x) {
           int bl, br;
           if (x == NULL)
              return 0;
           bl = treebalanced(x->l);
           br = treebalanced(x->r);
           if (bl < 0 || br < 0)    return -1;
           if (bl == br)            return bl + 1;
           if (bl == br + 1)        return bl + 1;
           if (bl == br - 1)        return br + 1;
           return -1;
        }

             
 7.  0.  It doesn't matter what the input tree looks like, this function
     always returns 0.