22C:21: Computer Science II: Data Structures

Quiz 10: December 10, 2004

1. Suppose the following elements are inserted into an empty binary search tree in the given order. Show the resulting binary search tree.

					4 15 8 18 9 11 10

Solution:

2. Reorder the sequence 4 15 8 18 9 11 10 so that when elements are inserted in this new order into an empty binary search tree, the resulting tree has height 3. Recall that by "height" I mean the number of nodes in the longest path from root to leaf.
Solution:

				10 8 15 4 9 11 18

3. The BinaryTree class in Bailey's structure package has the following fields:

    protected Object val; // value associated with node
    protected BinaryTree parent; // parent of node
    protected BinaryTree left, right; // children of node
    public static final BinaryTree EMPTY = new BinaryTree();

Just to help you understand the class better, here is a constructor from the BinaryTree class that takes a value and constructs a binary tree with a single node, containing that value.

    public BinaryTree(Object value)
    {
	val = value;
	parent = null;
	left = right = EMPTY;
    }

Write a member function of this class that returns the length of a shortest path from the root to a leaf. Use the following function header:

		int lengthToClosestLeaf()

For example, in the binary tree

the above function should return the value 1 because we need to go down just one link to the left from the root to get to a leaf.
Hint: It would be very hard to do this without recursion - so think recursively!

			int lengthToClosestLeaf()
			{
				if((left == EMPTY) || (right == EMPTY))
					return 0;
				else
					return 1+min(left.lengthToClosestLeaf(), right.lengthToClosestLeaf());
			}