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:**
4
\
15
/ \
8 18
\
9
\
11
/
10

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