Written Assignment #1

Text [1]: Page 46     Problems 1, 3, 5, 6, 11

1. Consider a binary tree of height n. Suppose that each node in a binary tree
   requires 3 units of storage - that is, one for the data and one for each of
   the two pointer fields. When is it preferable to use a complete binary tree
   array representation to a binary tree with pointers?

3. Recall the definition of an extended binary tree as a binary tree such that
   each of its non-empty nodes has two sons. This means that every leaf node
   has a null left son and a null right son. Prove that an extended binary
   tree of n nodes has n+1 null sons.

5. Is it true that the leaf nodes appear in the same relative order for the
   preorder, inorder, and postorder traversals of a binary tree?

6. Give an order for visiting the nodes of a binary tree that yields the
   reverse of preorder. 

11. Describe how to find the inorder predecessor of an arbitrary node in an
    unthreaded binary tree by making use of FATHER pointers if necessary.