Binary Search Trees

class Node:
    def __init__(self, value=None, left=None, right=None):
        self.value = value # information that is being stored in the tree
        self.left = left   # the left child (subtree)
        self.right = right # the right child (subtree)

    def __str__(self):
        return node.value

def b_list_depth_first(node):
    if not node:
        return []
    result = []
    if node.left:
        # append the left subtree's values
        result = result + b_list_depth_first(node.left)
    if node.value:
        # append this node's value
        result.append(node.value)
    if node.right:
        # append the right subtree's values
        result = result + b_list_depth_first(node.right)
    return result

def b_list_breadth_first(node):
    result = []
    nodelist = [node]
    # nodelist contains the nodes for height n
    while nodelist:
        # next_nodelist will contain the nodes for height n+1
        next_nodelist = []
        for subnode in nodelist:
            # append the current node's value to the result list
            result.append(subnode.value)
            # append the current node's children to next_nodelist
            if subnode.left:
                next_nodelist.append(subnode.left)
            if subnode.right:
                next_nodelist.append(subnode.right)
        nodelist = next_nodelist

    return result

def b_insert(node, value):
    if not node.value:
        node.value = value
    if value < node.value:
        node.left = node.left or Node()
        b_insert(node.left, value)
    elif value > node.value:
        node.right = node.right or Node()
        b_insert(node.right, value)

def b_delete(node, value, parent=None):
    if not node:
        return
    elif value < node.value:
        b_delete(node.left, value, parent=node)
    elif value > node.value:
        b_delete(node.right, value, parent=node)
    else:
        # CASE 1: remove the node from its parent
        if not node.left and not node.right:
            if parent.left and node == parent.left:
                parent.left = None
            else:
                parent.right = None

        # CASE 3: two children...
        elif node.left and node.right:
            successor = node.right
            successor_parent = node
            while successor.left:
                successor_parent = successor
                successor = successor.left
            node.value = successor.value
            b_delete(successor, successor.value, parent=successor_parent)

        # CASE 2: replace the node with its child
        else:
            if parent.left and node == parent.left:
                if node.left:
                    parent.left = node.left
                if node.right:
                    parent.left = node.right
            else:
                if node.left:
                    parent.right = node.left
                if node.right:
                    parent.right = node.right