please complete the todo:

~~~~~~~~~~~~~~~~~~~

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;

}