search trees ( ( parent null figure inserting new node into binary search tree(asearching for the node' location and (blinking the new node into the tree linkas illustrated in figure (anotice that this is the exact location where the new key needs to be inserted we can use modified version of the search operation to insert new keys into binary search treeas shown in listing to describe how the recursive method workssuppose we want to insert key value into the tree we built by hand in figure figure illustrates the method' view of the tree in each invocation and shows the changes to the tree as the specific instructions are executed remembergiven the recursive definition of binary treeeach node is itself the root of subtree as the bstinsert(recursive method navigates through listing insert key into binary tree class bstmap adds new entry to the map or replaces the value of an existing key def addselfkeyvalue )find the node containing the keyif it exists node self _bstsearchkey if the key is already in the treeupdate its value if node is not none node value value return false otherwiseadd new entry else self _root self _bstinsertself _rootkeyvalue self _size + return true helper method that inserts new itemrecursively def _bstinsertselfsubtreekeyvalue )if subtree is none subtree _bstmapnodekeyvalue elif key subtree key subtree left self _bstinsertsubtree leftkeyvalue elif key subtree key subtree right self _bstinsertsubtree rightkeyvalue return subtree