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");
}
Explanation / Answer
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[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. if (item n.items[0] && item n.items[1]) return contains(n.subtrees[2], item); return true; } // 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"); }Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.