EXERCISES ON BINARY TREES



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

 2. (Sedgewick, Exercise 5.79).  Give the preorder, inorder, postorder,
    and level-order traversals of the following binary trees.


 3. (a)  Write a function that counts the number of items in a binary tree.

    (b)  Write a function that returns the sum of all the keys in a binary tree.

    (c)  Write a 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.

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

 5. (a)  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.

    (b)  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.

 6. 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.
    
 7. What value does the following C function return when called with each of the
    binary trees in question 2?

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