bst.py

class Node:
    def __init__(self, data):
        self.data = data
        self.lchild = None
        self.rchild = None

    def insert(self, key):
        if key < self.data:
            if self.lchild:
                self.lchild.insert(key)
            else:
                self.lchild = Node(key)
        elif key > self.data:
            if self.rchild:
                self.rchild.insert(key)
            else:
                self.rchild = Node(key)

    def inorder_traversal(self):
        if self.lchild:
            self.lchild.inorder_traversal()
        print self.data
        if self.rchild:
            self.rchild.inorder_traversal()


class BST:

    def __init__(self):
        self.root = None

    def insert(self, key):
        if not self.root:
            self.root = Node(key)
        else:
            self.root.insert(key)

    def inorder(self):
        if self.root:
            self.root.inorder_traversal()

    def find_parent(self, key):
        cur = self.root

        while (cur.lchild or cur.rchild):
            if key < cur.data:
                if cur.lchild:
                    if key == cur.lchild.data:
                        return cur
                    else:
                        cur = cur.lchild
                else: break
            elif key > cur.data:
                if cur.rchild:
                    if key == cur.rchild.data:
                        return cur
                    else:
                        cur = cur.rchild
                else: break

    # splice out leftmost node of right subtree
    # this node might have at most one rchild
    def splice_successor(self, node):
        cur = node.rchild

        if not node.rchild.lchild:
            node.rchild = None
            return cur

        while (cur.lchild.lchild):
            cur = cur.lchild

        succ = cur.lchild
        if succ.rchild:
            cur.lchild = succ.rchild
        else:
            cur.lchild = None
        succ.rchild = None
        return succ

    def remove_node(self, k):
        p = self.find_parent(k)
        n = p.lchild if p.lchild.data == k else p.rchild

        if not n.lchild and not n.rchild:
            if p.lchild == n:
                p.lchild = None
            elif p.rchild == n:
                p.rchild = None
        elif n.lchild and n.rchild:
            succ = self.splice_successor(n)
            succ.lchild = n.lchild
            succ.rchild = n.rchild
            if p.lchild == n:
                p.lchild = succ
            elif p.rchild ==n:
                p.rchild = succ
        else:
            child = n.lchild if n.lchild else n.rchild
            if p.lchild == n:
                p.lchild = child
            elif p.rchild == n:
                p.rchild = child

        n = None
        return



t = BST()
t.insert(19)
t.insert(67)
t.insert(13)
t.insert(25)
t.insert(100)
t.insert(80)

t.inorder()
n = t.remove_node(67)
t.inorder()