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 is not 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 self.__balance(node)

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

    def __recursive_remove(self,value,node):
        if node is not 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 is None and node.right is None:
                    node=None
                elif node.left is None:
                    node=node.right
                elif node.right is None:
                    node=node.left
                else:
                    min_right_value=self.__recursive_find_right_subtree_min(node.right)
                    node.right=self.__recursive_remove(min_right_value,node.right)
                    node.value=min_right_value
            return self.__balance(node)
        raise ValueError

    def __recursive_find_right_subtree_min(self,node):
        if node.left is not None:
            return self.__recursive_find_right_subtree_min(node.left)
        return node.value

    def in_order(self):
        if self.__root is 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 is None:
            return ""
        elif node.left is None and node.right is 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 is 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 is None:
            return ""
        elif node.left is None and node.right is 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 is 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 is None:
            return ""
        if node.left is None and node.right is 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 is None:
            return 0
        return self.__root.height

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

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

    def __balance(self,node):
        if node is not None:
            if self.__get_subtree_balance(node)>1:
                if self.__get_subtree_balance(node.right)<0:
                    node.right=self.__rotate_right(node.right,node.right.left)
                node=self.__rotate_left(node,node.right)
            elif self.__get_subtree_balance(node)<-1:
                if self.__get_subtree_balance(node.left)>0:
                    node.left=self.__rotate_left(node.left,node.left.right)
                node=self.__rotate_right(node,node.left)
            self.__update_node_height(node)
        return node

    def __get_subtree_balance(self,node):
        right_subtree_height=0
        left_subtree_height=0
        if node.right is not None:
            right_subtree_height=node.right.height
        if node.left is not None:
            left_subtree_height=node.left.height
        return right_subtree_height-left_subtree_height

    def __rotate_left(self,root_node,node):
        root_node.right=node.left
        node.left=root_node
        self.__update_node_height(root_node)
        self.__update_node_height(node)
        return node

    def __rotate_right(self,root_node,node):
        root_node.left=node.right
        node.right=root_node
        self.__update_node_height(root_node)
        self.__update_node_height(node)
        return node

    def to_list(self):
        if self.__root is None:
            return []
        return self.__recursive_to_list(self.__root)

    def __recursive_to_list(self,node):
        if node is None:
            return []
        return self.__recursive_to_list(node.left)+[node.value]+self.__recursive_to_list(node.right)

# if __name__ == '__main__':