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