import java.util.LinkedList;

public class TwoThreeIntSet {

private class Node { int[] items; // the keys/items in the node Node[] subtrees; // the children of this node int nodeType; // the node type (2, 3, or 4)

/** * Create a new node with item as the key and two subtrees * * @param item the key/item for the node * @param left the root of the subtree less than the item * @param right the root of the subtree greater than the item */ public Node(int item, Node left, Node right) { items = new int[3]; subtrees = new Node[4]; subtrees[0] = left; subtrees[1] = right; nodeType = 2; items[0] = item; }

/** * Creates a new leaf with item as the key. * * @param item the key/item for the leaf. */ public Node(int item) { this(item, null, null); }

/** * Returns true if this node is a leaf * * @return true if this node is a leaf. */ public boolean isLeaf() { return subtrees[0] == null; } }

private Node root;

public TwoThreeIntSet() { }

// DO NOT MODIFY ANYTHING ABOVE THIS LINE

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"); }

/** * Inserts item into the 2-3 tree. * * @param item the number to be inserted into the tree. */ public void put(int item) { /* * If the tree is empty, create a new leaf node for the item. It is also the * root of the tree. */ if (root == null) root = new Node(item);

/* * Otherwise, we will be inserting the item in a pre-existing leaf using a * recursive helper function. */ else { root = put(root, item); /* * The recursive helper function returns a 2-3 tree where the root might be a * 4-node. Check for this and split if necessary. */ if (root.nodeType == 4) { Node left = new Node(root.items[0], root.subtrees[0], root.subtrees[1]); Node right = new Node(root.items[2], root.subtrees[2], root.subtrees[3]); root = new Node(root.items[1], left, right); } } }

/** * A recursive helper function. * * @param n the root of a 2-3 tree into which we will insert a number * @param item the number to be inserted. * @return the root of new tree with item inserted. Note that this root might * now be a 4 node. */ private Node put(Node n, int item) { /* * First check if n contains item. If it does, there is nothing to do and we can * return the root of this subtree unchanged */ int itemCount = n.nodeType - 1; for (int i = 0; i < itemCount; i++) { if (n.items[i] == item) return n; }

/* * Because we always insert into a pre-existing leaf, the base case here is a * tree with one node (the root is a leaf). */ if (n.isLeaf()) {

// If the node is a 2-node, insert the new item to its left or right. if (n.nodeType == 2) { if (item < n.items[0]) { n.items[1] = n.items[0]; n.items[0] = item; } else { n.items[1] = item; } n.nodeType = 3; }

else if (n.nodeType == 3) { // TODO // Turn this into a 4-node and return it since you are allowed // to temporarily have a 4-node as a the root. throw new RuntimeException("Implement me"); }

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

return n; }

} else if (n.nodeType == 3) { // TODO throw new RuntimeException("Implement me!"); } else throw new RuntimeException("ERROR: " + n.nodeType + "-node found while inserting");

} }