class Binary_Search_Tree:

    class __BST_Node:

        def __init__(self, value):
            self.value = value
            self.left=None
            self.right=None
            self.height=0

    def __init__(self):
        self.__root = None

    def insert_element(self, value):
        self.__root=self.__recursive_insert(value,self.__root)

    def __recursive_insert(self,value,node):
        if node!=None:
            if value<node.value:
                node.left=self.__recursive_insert(value,node.left)
            elif value>node.value:
                node.right=self.__recursive_insert(value,node.right)
            else:
                raise ValueError
        else:
            node=self.__BST_Node(value)
        self.__update_node_height(node)
        return node

    def remove_element(self, value):
        self.__root=self.__recursive_remove(value,self.__root)

    def __recursive_remove(self,value,node):
        if node!=None:
            if value<node.value:
                node.left = self.__recursive_remove(value,node.left)
                self.__update_node_height(node)
            elif value>node.value:
                node.right = self.__recursive_remove(value,node.right)
                self.__update_node_height(node)
            else:
                if node.left==None:
                    node=node.right
                elif node.right==None:
                    node=node.left
                else:
                    min_right_value=self.__recursive_find_right_subtree_min(node.right)
                    self.__recursive_remove(min_right_value,node)
                    node.value=min_right_value
            return node
        else:
            raise ValueError

    def __recursive_find_right_subtree_min(self,node):
        if node.left==None:
            return_value=node.value
            return return_value
        else:
            self.__recursive_find_right_subtree_min(node.right)

    def in_order(self):
        if self.__root==None:
            return "[ ]"
        init_string=self.__recursive_inorder(self.__root)
        init_string=init_string[:-2]
        return_string= "[ "+init_string+" ]"
        return return_string

    def __recursive_inorder(self,node):
        if node==None:
            return ""
        elif node.left==None and node.right==None:
            return str(node.value) +", "
        else:
            return self.__recursive_inorder(node.left)+str(node.value)+", "+self.__recursive_inorder(node.right)

    def pre_order(self):
        if self.__root==None:
            return "[ ]"
        init_string=self.__recursive_preorder(self.__root)
        init_string=init_string[:-2]
        return_string= "[ "+init_string+" ]"
        return return_string

    def __recursive_preorder(self,node):
        if node==None:
            return ""
        elif node.left==None and node.right==None:
            return str(node.value) + ", "
        else:
            return str(node.value)+", "+self.__recursive_preorder(node.left)+self.__recursive_preorder(node.right)

    def post_order(self):
        if self.__root==None:
            return "[ ]"
        init_string=self.__recursive_postorder(self.__root)
        init_string=init_string[1:]
        return_string= "["+init_string+" ]"
        return return_string

    def __recursive_postorder(self,node):
        if node==None:
            return ""
        elif node.left==None and node.right==None:
            return ", "+str(node.value)
        else:
            return self.__recursive_postorder(node.left)+self.__recursive_postorder(node.right)+", "+str(node.value)

    def get_height(self):
        if self.__root==None:
            return 0
        return self.__root.height

    def __update_node_height(self,node):
        if node.left!=None and node.right!=None:
            if node.right.height>=node.left.height:
                node.height=node.right.height+1
            else:
                node.height=node.left.height+1
        elif node.left==None and node.right!=None:
            node.height=node.right.height+1
        elif node.right==None and node.left!=None:
            node.height=node.left.height+1
        else:
            node.height=1

    def __str__(self):
        return self.in_order()

# if __name__ == '__main__':