EXERCISES ON BINARY TREES AND BINARY SEARCH TREES

READING 
-------
Sedgewick, 217-223, 230-241, 477-508


EXERCISES
---------

 1. Give the inorder and postorder traversal for the tree whose preorder
    traversal is A B C - - D - - E - F - -.  The letters correspond to
    labelled internal nodes; the minus signs to external nodes.

 2. Sedgewick, Exercise 5.79

 3. Give the stack contents, in the style of Figure 5.27, for the
    preorder, inorder, and postorder traversals of the center tree
    in Exercise 5.79.

 4. Write a C function that counts the number of items in a binary tree.

 5. Write a C function that returns the sum of all the keys in a binary tree.

 6. Write a C function that returns the maximum value of all the keys in
    a binary tree. Assume all values are nonnegative; return -1 if the
    tree is empty.

 7. Write a C function that prints all the keys less than a given value v
    in a binary tree. 

 8. The height of a tree is the maximum number of nodes on a path from the
    root to a leaf node. Write a C function that returns the height of a
    binary tree.

 9. The cost of a path in a tree is sum of the keys of the nodes participating
    in that path. Write a C function that returns the cost of the most expensive
    path from the root to a leaf node.

10. A binary tree is said to be "balanced" if both of its subtrees  
    are balanced and the height of its left subtree differs from the
    height of its right subtree by at most 1.  Write a C function to
    determine whether a given binary tree is balanced.
    
11. Write a C function that determines whether a given binary tree
    is a binary serach tree. 

12. What value does the following C function return when called with the
    binary trees in Sedgewick 5.79?

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



                 ------------------------------------
		 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.
        int treecount(link x) {
           if (x == NULL)
              return 0;
           else
              return 1 + treecount(x->l) + treecount(x->r);
        }

 5. Write a C function that returns the sum of all the keys in a binary tree.

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

 6. It is convenient to use the helper max3 function from the Functions exercises.

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

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

 8. We use the max function from the Functions exercises.

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

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

10. 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;
        }

             
11. Be sure to handle case when left and/or right child is NULL.

        int isBST(link x) {
           if (x == NULL)  
              return 1;    
           else if (x->l == NULL && x->r == NULL)
              return 1;
           else if (x->l == NULL && x->key <= x->r->key)
              return isBST(x->r);
           else if (x->r == NULL && x->key >= x->l->key)
              return isBST(x->l);
           else if (x->key <= x->r->key  &&  x->key >= x->l->key)
              return (isBST(x->l) && isBST(x->r));
        }

12. This function serves little purpose: it always returns 0.