(asplitting the left child kp kp kl kn km kl kr kn km kr (bsplitting the middle child kp kp kl km kn kl kr km kn kr (csplitting the right child kp kp kl km kr kn kl km kr kn figure inserting the promoted key and reference into full parent node left child and new child node becomes its middle child splitting the root node results in new level being added to the tree implementation the - tree insertion is best implemented recursively rememberto insert new itemnot only do we have to navigate down into the tree to find leaf nodebut we may also have to split the nodes along the path as we backtrack to the root node the implementation of the - tree insertion is provided in listing the insert(method handles the two special cases involving the root nodethe insertion of the first keyresulting in the creation of the first nodeand splitting the root noderesulting in new tree level if the tree is not initially emptythe before after figure splitting the root node is special case