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 D B A C 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 C D G F I H E 
    level-order   D B F A C E G        C B D A E        E D H B C F I A G

 3.       preorder        inorder        postorder
           C*              C*             C*
           C  B* D*        B* C  D*       B* D* C
           B* D*           A* B  C  D*    A* B  D* C
           B  A* D*        A  B  C  D*    A  B  D* C
           A* D*           B  C  D*       B  D* C
           A  D*           C  D*          D* C
           D*              D*             E* D  C
           D E*            D  E*          E  D  C 
           E*              E*             D  C
           E               E              C 


 4. (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.

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

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


 6. (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));
           }

 7. 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 = balanced(x->l);
           br = balanced(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;
        }

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