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
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.
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:
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!
if((left == EMPTY) || (right == EMPTY))
return 1+min(left.lengthToClosestLeaf(), right.lengthToClosestLeaf());