search trees listing insert new key into - tree class tree map def insertselfkeynewitem )if the tree is emptya node has to be created for the first key if self _root is none self _root treenodekeynewitem otherwisefind the correct leaf and insert the key else (pkeypdatapref_ insertself _rootkeynewitem see if the node was split if pkey is not none newroot treenodepkeypdata newroot left self _root newroot middle pref self _root newroot recursive function to insert new key into the tree def recinsertsubtreekeynewitem )make sure the key is not already in the tree if subtree haskeykey return (nonenonenoneis this leaf nodeelif subtree isaleaf(return addtonodesubtreekeynewitemnone otherwiseit' an interior node else which branch do we takebranch subtree getbranchkey (pkeypdatapref_ insertbranchkeynewitem if the child was splitthe promoted key and reference have to be added to the interior node if pkey is none return (nonenonenoneelse return addtonodesubtreepkeypdatapref recursive recinsert(method is called to insert the new key this method navigates the tree to find the leaf node into which the key is to be inserted during the unwinding of the recursionthe function checks to see if the child node was splitand if it wasadds the promoted key and reference to the current interior node the addtonode()provided in listing is used to insert key into both leaf and interior nodes when the key is inserted into an interior nodethe key argument will contain the promoted key and pref will contain the promoted reference to insert new key into leaf nodethe key argument contains the new key and pref will be none if there is room for the new keythe function arranges the keys and the links in the proper order and null references are returned in