/** * 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. */ Could you please solve the TODOs? I have tried other solutions but they do not return the correct answer.  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; } // 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"); } }

Expected :(150|250),(88|100),(200|201),(251|300) Actual :(251|201),(0),(0),(0)