please complete the TODO. It is asking for the case: If not a leaf node, we will need to insert in one of our subtrees.?

~~~~~~~

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) {

if (item < n.items[0]) {

n.items[2] = n.items[1];

n.items[1] = n.items[0];

n.items[0] = item;

} else if(item > n.items[0] && item < n.items[1]){

n.items[2] = n.items[1];

n.items[1] = item;

} else if(item > n.items[1]) {

n.items[2] = item;

}

n.nodeType = 4;

}

else

return n;

}

// If not a leaf node, we will need to insert in one of our subtrees.

else {

if (n.nodeType == 2) {

if (item < n.items[0]) {

Node result = put(n.subtrees[0], item);

// if the resulting root is not a 4-node, we can insert it as our new left.

if (result.nodeType != 4) {

n.subtrees[0] = result;

}

// otherwise, we need to fix it by splitting it

else {

Node newLeft = new Node(result.items[0], result.subtrees[0], result.subtrees[1]);

Node newMiddle = new Node(result.items[2], result.subtrees[2], result.subtrees[3]);

n.items[1] = n.items[0];

n.items[0] = result.items[1];

n.subtrees[2] = n.subtrees[1];

n.subtrees[1] = newMiddle;

n.subtrees[0] = newLeft;

n.nodeType = 3;

}

} else {

Node result = put(n.subtrees[1], item);

// if the resulting root is not a 4-node, we can insert it as our new right.

if (result.nodeType != 4) {

n.subtrees[1] = result;

}

// otherwise, we need to fix it by splitting it

else {

Node newMiddle = new Node(result.items[0], result.subtrees[0], result.subtrees[1]);

Node newRight = new Node(result.items[2], result.subtrees[2], result.subtrees[3]);

n.items[1] = result.items[1];

n.subtrees[2] = newRight;

n.subtrees[1] = newMiddle;

n.nodeType = 3;

}

}

return n;

} else if (n.nodeType == 3) {

// TODO

throw new RuntimeException("Implement me!");

} else

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

}

return n;

}