week 10: Mutating BST

 There are two situations that we will mutate a BST. One is inserting, but it does not change the topological structure of BST, so here I will just talk about deleting.

 

 Here is BST, and they are three cases we may encounter when deleting nodes from it.

  Case 1: Deleting one leaf from it, which means the node we want to delete has None as children. This is simple, we just delete from the BST and would not break the structure of the tree.

  Case 2: Deleting a node with only child. In this case, we just need to delete the node and link its only child to the parent of the original node. For example, if we delete 72 from the BST, we just need to put 67 to the right child of 54.

  Case 3: This is a bit trickier. Using recursion could make the process easier. What we need to do is first finding the node with minimum value rooted at the node we want to delete. Note that this is just a convention, theoretically we can find the maximum from the left child. After finding the node, we replace the target node's value with the minimum and delete the node with minimum value from the new node. So if we delete 17, we will find 19 to be smallest from 17's right children. Replacing 17 with 19 and delete 19 from its previous position then we are done.

Here is a code we implement the actual method.

    return_node = node
    if not node:
        pass
    elif data < node.data:
        node.left = delete(node.left, data)
    elif data > node.data:
        node.right = delete(node.right, data)
    elif not node.left:
        return_node = node.right
    elif not node.right:
        return_node = node.left
    else:
        node.data = _find_max(node.left).data
        node.left = delete(node.left, node.data)
    return return_node

But I noticed this may not work with BST that has duplicate nodes. One way to solve this from what I learned is that passing the address as well when we want to delete the node. The motivation is that address is unique for each node.