sec - trees figure simple insert into the - tree of figure the value is inserted into the tree at the leaf node containing because there is room in the node for second keyit is simply added to the left position with moved to the right position private findhelp(ttnode rootkey kif (root =nullreturn null/val not found if ( compareto(root lkey()= return root lval()if ((root rkey(!null&( compareto(root rkey()= )return root rval()if ( compareto(root lkey() /search left return findhelp(root lchild() )else if (root rkey(=null/search center return findhelp(root cchild() )else if ( compareto(root rkey() /search center return findhelp(root cchild() )else return findhelp(root rchild() )/search right insertion into - tree is similar to insertion into bst to the extent that the new record is placed in the appropriate leaf node unlike bst insertiona new child is not created to hold the record being insertedthat isthe - tree does not grow downward the first step is to find the leaf node that would contain the record if it were in the tree if this leaf node contains only one valuethen the new record can be added to that node with no further modification to the treeas illustrated in figure in this examplea record with key value is inserted searching from the rootwe come to the leaf node that stores we add as the left value (pushing the record with key to the rightmost positionif we insert the new record into leaf node that already contains two recordsthen more space must be created consider the two records of node and the record to be inserted without further concern for which two were already in and which is the new record the first step is to split into two nodes thusa new node -call it -must be created from free store receives the record with the least of the three key values receives the greatest of the three the record