Please fill in the to-do: public boolean contains(int item) { return contains(ro
ID: 3710523 • Letter: P
Question
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");
}