The tricky one is deletion. The idea is the following:

Case #1: node is a leaf:
    if parent:
        link parent.left or parent.right to None
     else:
        delete root key

Case #2: node has one child:
     find the successor
     if parent:
         link parent with successor
     else:
         root node key = successor.key
         set root child to None

Case #3: node has two children:
     find successor (smallest node bigger than node)
     set node.key = successor.key
     (successor's parent).left/right = successor.right

And here we go with the code.

def preorder(tree):
    if tree:
        print tree.key,
        preorder(tree.left)
        preorder(tree.right)


class Node(object):
    def __init__(self, value):
        self.key = value
        self.left = None
        self.right = None


    def insert(self, value):
        if value < self.key:
            if self.left is None:
                self.left = Node(value)
            else:
                self.left.insert(value)
                
        elif value > self.key:
            if self.right is None:
                self.right = Node(value)
            else:
                self.right.insert(value)


    # the straightforward version
    def lookup(self, value):
        if self.key == value:
            return self
        elif value < self.key:
            if self.left is None:
                return None
            return self.left.lookup(value)
        else:
            if self.right is None:
                return None
            return self.right.lookup(value)


    # returns both node and parent node; used for delete()
    def lookupParent(self, value, parent=None):
        if self.key == value:
            return self, parent
        elif value < self.key:
            if self.left is None:
                return None, None
            return self.left.lookupParent(value, self)
        elif value > self.key:
            if self.right is None:
                return None, None
            return self.right.lookupParent(value, self)


    # recursive version
    def findMin(self):
        if self.left is None:
            return self

        return self.left.findMin()

    
    # iterative version
    def findMax(self):
        maxNode = self
        while maxNode.right is not None:
            maxNode = maxNode.right

        return maxNode


    def delete(self, value):
        node, parent = self.lookupParent(value)

        # key does not exist
        if node is None:
            return

        # CASE #1, node is a leaf
        if node.right is None and node.left is None:
            if parent:
                if parent.left is node:
                    parent.left = None
                else:
                    parent.right = None
            # key is in the root node
            else:                
                self.key = None

        # CASE #2, node has one child
        elif node.right is None or node.left is None:
            # find the successor
            if node.left:
                successor = node.left
            else:
                successor = node.right
            # if there is a parent, link parent with successor
            if parent:
                if parent.left is node:
                    parent.left = successor
                else:
                    parent.right = successor
            # key is in the root node
            else:
                node.key = successor.key
                node.left = None
                node.right = None

        # CASE #3, node has two childs
        else:
            parent = node
            successor = node.right
            while successor.left:
                parent = successor
                successor = successor.left

            node.key = successor.key

            # fix successor's parent's child
            if parent.left == successor:
                parent.left = successor.right
            else:
                parent.right = successor.right



root = Node(10)
root.insert(3)
root.insert(44)
root.insert(1)
root.insert(5)
root.insert(4)
root.insert(6)
root.insert(99)

preorder(root)
print
root.delete(3)
print
preorder(root)