search trees before ** after ** figure inserting key into - tree with space available in the leaf node before ** after ** figure inserting key into - tree with space available in the leaf node splitting leaf node things become more complicated when the leaf node is full suppose we want to insert value into our sample tree the search for the node leads to the leaf node containing keys and as shown in figure based on the search property of the - treethe new key belongs in this leaf nodebut it' full you might be tempted to create new leaf node and attach it to the full node as child this cannot be donehoweversince all leaf nodes must be at the same level and all interior nodes must have at least two children insteadthe node has to be splitresulting in new node being created at the same level before after ** ** figure inserting key into - tree with full leaf node