class Node(object):
    def __init__(self, data):
        self.data = data
        self.leftChild = None
        self.rightChild = None

class BinarySearchTree(object):
    def __init__(self):
        self.root = None

    def traverse(self):
        if self.root:
            self.traverseInOrder(self.root)

    def traverseInOrder(self, node):
        if node.leftChild:
            self.traverseInOrder(node.leftChild);

        print("%s " % node.data)

        if node.rightChild:
            self.traverseInOrder(node.rightChild)
        
    def insert(self, data):
        if not self.root:
            self.root = Node(data)
        else:
            self.insertNode(data, self.root)

    def insertNode(self, data, node):
        if data < node.data:
            if node.leftChild:
                self.insertNode(data, node.leftChild)
            else:
                node.leftChild = Node(data)
        else:
            if node.rightChild:
                self.insertNode(data, node)
            else:
                node.rightChild = Node(data)

    def remove(self, data):
        if self.root:
            self.root = self.removeNode(data, self.root);

    def removeNode(self, data, node):
        if not node:
            return node;

        if data < node.data:
            node.leftChild = self.removeNode(data, node.leftChild)
        elif data > node.data:
            node.rightChild = self. removeNode(data, node.rightChild)
        else:
            if not node.leftChild and not node.rightChild:
                print('Removing a leaf node ... ')
                del node
                return None;

            if not node.leftChild:
                print("Removing a node iwth single right child ...")
                tempNode = node.rightChild
                del node
                return tempNode;
            elif not node.rightChild:
                print("Removing a node with single left child ...")
                tempNode = node.leftChild
                del node
                return tempNode;

            print("Removing node with two childern ...")
            tempNode = self.getPredecessor(node.leftChild)
            node.data = tempNode.data
            node.leftChild = self.removeNode(tempNode.data, node.leftChild)

        return node;

    def getPredecessor(self, node):
        if node.rightChild:
            return self.getPredecessor(node.rightChild)

        return node;

bst = BinarySearchTree()
bst.insert(6)
bst.insert(4)
bst.insert(5)
bst.traverse()

bst = BinarySearchTree()
bst.insert(6)
bst.insert(7)
bst.insert(5)
bst.insert(4)

bst.remove(6)

bst.traverse()