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)); }