Holy Mutations! Things getting dicey from now on...

We have done a lot work traversing trees and linking nodes. While it has been all fun, we now need to step things up a notch: we need to mutate the contents inside these trees and linking nodes. Let us remember that the data in each node is mutatable, and thus can be changed at any spot in time. Let us observe at one of the examples of mutation, in this case, of binary search trees.

Delete in Binary Search Trees
Algorithm
(Note: Remember that in a BST, the left child is smaller than the node, and the right child is bigger than the node)

1. If the node is not a node, then there is nothing to do
2. If data is less than the data in the node, go down the left (which has smaller values)
3. If data is more than the data in the node, go down the right (which has bigger values)
4. If node has fewer than two children, then return the existing one (which essentially brings down the only child if the deleted node has only got one child)
5. Otherwise, if both children exist, replace the data with the data in the largest child in the left subtree and recursively work on the data from the left node, and finally return that node

On this final step, it is important to notice that, when deleting an element from a BST, you need to pull the item from the left child since the right child is always bigger than the node. To make this clear, we could follow this example:

            8
        6
    5
            4
        3
2
    1

Let's delete the five (5). Then we need to to grab a value to replace the five, and it only makes sense to take the largest child from the left. In this case it would be the four (4). The four is still smaller than the rest of the right children, and bigger than the left children. Then we would get the following:

            8
        6
    4
        3
2
    1

Code

This code was taken from class, so credit to whoever wrote it! It is shown here to give more context to what was done above.

def delete(node, data):
    ''' (BTNode, data) -> BTNode

    Delete, if it exists, node with data and return resulting tree.

    >>> b = BTNode(8)
    >>> b = insert(b, 4)
    >>> b = insert(b, 2)
    >>> b = insert(b, 6)
    >>> b = insert(b, 12)
    >>> b = insert(b, 14)
    >>> b = insert(b, 10)
    >>> b = delete(b, 12)
    >>> print(b)
            14
        10
    8
            6
        4
            2
    <BLANKLINE>
    '''
    return_node = node
    if not node: # Step 1 from the algorithm
        pass
    elif data < node.data: # Step 2 from the algorithm
        node.left = delete(node.left, data)
    elif data > node.data: # Step 3 from the algorithm
        node.right = delete(node.right, data)
    elif not node.left: # Step 4 from the algorithm
        return_node = node.right
    elif not node.right: # Step 4, again, from the algorithm
        return_node = node.left
    else: # Step 5 from the algorithm
        node.data = _find_max(node.left).data
        node.left = delete(node.left, node.data)
    return return_node

There is a helper function that traverses the right children for the highest value. It is used on the function above so that the highest value from the left child branch is brought and used as the new data of the node, and everything is brought down the left children. After all, the highest value from the left child will be found on the left child's right branch.

def _find_max(node):
    ''' (BSTNode) -> BSTNode
    
    Return maximal node in the BST rooted at node.
    Assume node is not None.
    
    >>> b = BTNode(8)
    >>> b = insert(b, 4)
    >>> b = insert(b, 2)
    >>> b = insert(b, 6)
    >>> b = insert(b, 12)
    >>> b = insert(b, 14)
    >>> b = insert(b, 10)
    >>> _find_max(b).data
    14
    >>> _find_max(b.left).data
    6
    '''
    return _find_max(node.right) if node.right else node

The Challenge
I wish I could say this could is easy to understand. Once you analyze it, it makes sense how it works and what it does. Regardless, there is a difference between knowing what to do and knowing how it needs to be done. The algorithm is not that intuitive, and requires close attention to notice exactly why things happen, and then how.