search trees the base case is reached when the empty subtree is encountered after taking the left child link from node as shown in (part dat this pointa new tree node is created and its data field set to the new key (part ea reference to this new node is then returned and the recursion begins unwinding the first step in the unwinding takes us back to node the reference returned by the recursive call is assigned to the left field of the subtree noderesulting in the new node being linked into the tree as the recursion continues unwindingshown in parts ( )the current subtree reference is returned and relinked to its parent this does not change the structure of the tree since the same references are simply being reassigned this is necessary given the way we link the new node to its parent and to allow the method to be used with an initially empty tree when inserting the first key into the treethe root reference will be null if we called the method on an empty tree with self _bstinsertself _root )the new node will be created within the methodbut the reference to the new node is not assigned to the root field and the tree remains empty since method arguments are passed by value in pythonwe have to return the reference and explicitly assign it to the root field as is done in the add(method finallyafter the new item is added to the treethe size field is incremented by one to reflect this change you may have noticed the insertion method lacks final else clause on the conditional statementwhich would handle the case when the new key equals an existing key if duplicate key is encountered during the search phasewe simply return the subtree reference to stop the recursion and allow for proper unwinding deletions removing an element from binary search tree is bit more complicated than searching for an element or inserting new element into the tree deletion involves searching for the node that contains the target key and then unlinking the node to remove it from the tree when node is removedthe remaining nodes must preserve the search tree property there are three cases to consider once the node has been located the node is leaf the node has single child the node has two children the first step in removing an element is to find the node that contains the key this can be done in manner similar to that used when searching for the location to insert new element once the node is locatedit has to be unlinked to remove it from the tree we consider the three cases separately and then provide complete listing of the recursive bstremove(method and its use in implementing the remove(method