LAB 8 - SAMPLE ANSWERS

1.    Tree 1              Tree 2            Tree 5         Tree 6     Tree 7

            56                  56                  11        42      (empty)
          /    \               /  \                /
        34      78           34    78            22
       /  \    /  \         /  \                / 
     23   40  61  92      23   40             33
                              /  \           /
                             37  49        44
                                          /
                                        55
                                       etc.

      Tree 3              Tree 4

            56                   56  
          /    \               /    \   
        34      78           34      61 
       /  \                 /  \       \
     23    40             23   40       92
                              /  \     /
                             37  49   78


2. NOTE to Section L (8:30) students: the "sum" problem was changed to
   "count the nodes" for subsequent labs since this revised problem
   does not depend on the type of E being an Integer. Please review
   the new problem and the solution below.

	public int count() {
		return count(root);   // call private helper method
	}
	
	private int count(BTNode<E> node) {
		if (node == null)
			return 0;
		else
			return 1 + count(node.left) + count(node.right);
	}

3.
	
	public int height() {
		return height(root);
	}

	// The height of a tree rooted at the given node is 1 (for that node)
	// plus the height of its deeper subtree.
	private int height(BTNode<E> node) {
		if (node == null)
			return 0;
		else {
			int heightLeft = height(node.left);
			int heightRight = height(node.right);
			if (heightLeft > heightRight)
				return 1 + heightLeft;
			else
				return 1 + heightRight;
		}		
	}

4.
	
	public boolean isFull() {
		return isFull(root);
	}

	// The binary tree rooted at the given node is full 
	// if each subtree is full and each subtree has the same height.
	private boolean isFull(BTNode<E> node) {
		
		if (node == null)
			return true;
		else
			return (isFull(node.left) && isFull(node.right) 
				&& height(node.left)==height(node.right));
		
	}