class BinarySearchTreeNode : 

    def __init__(self, data ) : 
        self.data = data 
        self.left = None 
        self.right = None 

    def addChild(self , data) : 
        if data == self.data : 
            return 

        elif data < self.data : 
            if self.left == None : 
                self.left = BinarySearchTreeNode(data)

            else : 
                self.left.addChild(data)

        else : 
            if self.right == None :
                self.right = BinarySearchTreeNode(data)
            
            else : 
                self.right.addChild(data)

    def display(self , level = 0 ):

        if self.right : 
            self.right.display(level+1)

        print("      "*level + "--",self.data)

        if self.left : 
            self.left.display(level+1)

root = BinarySearchTreeNode(12)

root.addChild(7)
root.addChild(18)
root.addChild(2)
root.addChild(9)
root.addChild(15)
root.addChild(21)

root.display()

class BinarySearchTreeNode : 

    def __init__(self, data ) : 
        self.data = data 
        self.left = None 
        self.right = None 

    def delete(self , data):

        if self.data == data : 
            # write the remove logic 

            if self.right == None and self.left == None : 
                self.data = "None" 
                return 

            elif self.right == None and self.left != None : 
                self = self.left 
                return 

            elif self.left == None and self.right != None : 
                self = self.right 
                return

        elif data < self.data : 
            # search for data on left 
            self.left.delete(data)

        else : 
            self.right.delete(data)
            # search for data on right 

    def addChild(self , data) : 
        if data == self.data : 
            return 

        elif data < self.data : 
            if self.left == None : 
                self.left = BinarySearchTreeNode(data)

            else : 
                self.left.addChild(data)

        else : 
            if self.right == None :
                self.right = BinarySearchTreeNode(data)
            
            else : 
                self.right.addChild(data)

    def display(self , level = 0 ):

        if self.right : 
            self.right.display(level+1)

        print("      "*level + "--",self.data)

        if self.left : 
            self.left.display(level+1)

root = BinarySearchTreeNode(12)

root.addChild(7)
root.addChild(18)
root.addChild(2)
root.addChild(9)
root.addChild(15)
root.addChild(21)
root.addChild(1)

root.display()
print("==============")
root.delete(21)
root.display()
print("==============")
root.delete(2)
root.display()