BST/Term Test 2

    This week we went back to work with the binary search tree. We previously learned how BST work and its uses but we never really got to the code for inserting and deleting an item in a BST. The insert function was pretty easy to implement because if the item we are trying to insert into the tree is less than the current nodes item we would call the insert method on the current node's left tree, but if it's greater than the current node's item we would call the insert method on the current node's right tree (this is when recursion comes in handy because the insert method is constantly called again on different subtrees in the BST until the item we are trying to insert is in its right place). We also worked on the delete function for the BST. I'll be completely honest here... Implementing the delete function was not as easy as implementing the insert function because it required a lot more thought into the possible scenarios that would happen when we delete a node in a BST. We first come up with the algorithm in plain English to see what scenarios we needed to cover:

    # Algorithm for delete:
    # 1. If this node is None, return that
    # 2. If data is less than node.data, delete it from left child and
    #     return this node
    # 3. If data is more than node.data, delete it from right child
    #     and return this node
    # 4. If node with data has fewer than two children,
    #     and you know one is None, return the other one
    # 5. If node with data has two non-None children,
    #     replace data with that of its largest child in the left subtree,
    #     and delete that child, and return this node

    After coming up with the algorithm in English, we put it into code:

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 node is None:
        pass
    elif node.data > data:
        node.left = delete(node.left, data)
    elif node.data < data:
        node.right = delete(node.right, data)
    elif node.left is None:
        return_node = node.right
    elif node.right is None:
        return_node = node.left
    else:
        node.data = _find_max(node.left).data
        node.left = delete(node.left, node.data)
    return return_node

    We also had our second term test this week... I feel like a did quite well on the test because I made sure that I understood all the materials by going over the lecture slides and examples and also redoing the weekly labs. But I guess I won't know how well I really did on the test because the TA's are still on strike. Hopefully the strike will end soon...