CSCI 3333.3 Data Structures
Spring 2013
Suggested Solution to Homework #6

Exercises:

(1) (a)

Algorithm peek()
Input: IntegerStack s, an integeer stack
Output: the top element of s, without changing s. Retun null if s is empty.

if s.isEmpty() return null;
result = s.pop();
s.push(result);
return result;

(b)

Algorithm findMax()
Input: IntegerStack s
Output: the maximum integer found in s, without changing s. Retun null if s is empty.

if s.isEmpty() return null;
IntegerStack temp = new IntegerStack();
maxSoFar = s.pop();
temp.push(maxSoFar);
while (! s.isEmpty()) {
    currentInteger = s.pop()    
    if (currentInteger > maxSoFar) maxSoFar = currentInteger;
    temp.push(currentInteger);
}
while (! temp.isEmpty()) {
    s.push(temp.pop());
}
return maxSoFar;

(2) Proof by Mathematical induction.

Let N = number of nodes
Nf = number of full nodes
Nl = number of leaves.

To prove: Nl = Nf + 1

For N= 1, it is trivial that Nl = 1 and Nf = 0 and the assertion is true.
Assume the assertion is true for N = k.
For N = k+1, let node i be the (k+1)th node added as a leave.
If the parent of i has node i as the only a leaf, then the parent changes from a leaf node to an interiori node. Thus, both Nf and Nl do not change, and the assertion is still true.
If the parent of i now has two node, then it becomes a full not. Thus, both Nf and Nl will be incremented by 1 and the assertion is still true.

QED

(3)

Preorder traversal: ABDGHEIJLMCFK
Inorder traversal: GDHBIELJMACFK
Postorder traversal: GHDILMJEBKFCA

Program:

(1)

For BinaryNode.java, add:

    // Print tree rooted at current node using inorder traversal with indentation
    public void printInOrder(int identLevel)
    {
        if( left != null )
            left.printInOrder(identLevel+1);            // Left
        for (int i=0; i<identLevel; i++) System.out.print("    ");
        System.out.println( element);                   // Node
        if( right != null )
            right.printInOrder(identLevel+1);           // Right
    }

    /**
     * Return the sum of path lengths and size of the non-null binary tree rooted at t.
     * result[0]: sum of path lengths; result[1]: size
     */
     public static <AnyType> int[] sumPathAndSize( BinaryNode<AnyType> t )
    {   int[] result = {-1, 0};
        int[] childResult = new int[2];
        if( t != null )
        {
            result[0] = 0;
            result[1] = 1;
            if (t.left != null) {
                childResult = sumPathAndSize(t.left);
                result[0] = result[0] + childResult[0] + childResult[1];
                result[1] = result[1] + childResult[1];
            }
            if (t.right != null) {
                childResult = sumPathAndSize(t.right);
                result[0] = result[0] + childResult[0] + childResult[1];
                result[1] = result[1] + childResult[1];
            }
           
        }
        return result;
    }
 

For BinaryTree.java, add:

    public void printInOrderWithIdentation( )
    {
        if( root != null )
           root.printInOrder(0);
    }

    public float averageHeight( )
    {
        return BinaryNode.averageHeight( root );
    }