fig after splitting as result of inserting fig after inserting and fig inserting into the -tree causes splitting inserting an item causes one of two possible outcomes either the leaf node has room in it to add the new item or the leaf node splits resulting in middle value and new node being promoted to the parent this suggests recursive implementation is appropriate for inserting new item the recursive algorithm is given an item to insert and returns two valuesthe promoted key and the new right node if there is one and proceeds as follows if this is leaf node and there is room for itmake room and store the item in the node otherwise if this is leaf nodemake new node sort the new item and old items choose the middle item to promote to the parent take the items after the middle and put them into the new node return tuple of the middle item and new right node if this is non-leaf nodecall insert recursively on the appropriate subtree consult the return value of the recursive call to see if there is newly promoted key and right subtree if sotake the appropriate action to store the new item and subtree pointer in the node if there is no room to store the promoted valuesplit again as described in step this copy belongs to 'acha