Please fill in the to-do:

public boolean contains(int item) {

return contains(root, item);

}

private boolean contains(Node n, int item) {

// The base case here is empty tree. The item is not in the empty tree.

if (n == null)

return false;

// If the node is a 2-node, use normal BST search.

if (n.nodeType == 2) {

if (item < n.items[0])

return contains(n.subtrees[0], item);

if (item > n.items[0])

return contains(n.subtrees[1], item);

return true;

}

else if (n.nodeType == 3) {

// TODO

// If the node is a 3-node, we must check both items in this node. If neither is

// the item we are looking for, we must decide which of the three subtrees to

// search next.

throw new RuntimeException("Implement me");

}

// If this node is not a 2-node or a 3-node, this is an error

else

throw new RuntimeException("ERROR: " + n.nodeType + "-node found while searching");

}