
from typing import Callable, List, Any


class Node:
   """ Binary tree node. """

   def __init__(self, value):
      self.value: Any = value
      """ The node data. """
      self.left: Node = None
      """ The left child node, or None if there is not one. """
      self.right: Node = None
      """ The left child node, or None if there is not one. """


class BinaryTree:
   """ Binary tree. """

   def __init__(self, key=None):
      self.size: int = 0
      """ The node count. """
      self.root: Node = None
      """ The root node, or None if the tree is empty. """
      self.key: Callable[[Any], Any] = key


   def __len__(self) -> int:
      """ Gets the tree size.

   :return: The number of values in the tree.
   :rtype: int """
      return self.size


   def __str__(self):
      return str(self.as_list())


   def as_list(self) -> List:
      result: List = []
      self.fill_elements(self.root, result)
      return result


   def fill_elements(self, branch: Node, result: List) -> None:
      """ Recursively adds elements from a sub-tree to a list in order.

   :param branch The sub-tree to be listed.

   :pararm result The list to which elements will be added. """
      if branch.left is not None:
         self.fill_elements(branch.left, result)
      result.append(branch.value)
      if branch.right is not None:
         self.fill_elements(branch.right, result)


   def add(self, value: Any) -> None:
      """ Adds a value to the tree.

   :param value: the value to be added. """
      node: Node = Node(value)
      if self.root is None:
         self.root = node
         self.size += 1
      else:
         self.add_to_branch(self.root, node)


   def add_to_branch(self, branch: Node, node: Node) -> None:
      """ Adds a node to a sub-tree.

   :param branch the sub-tree to which the node will be added.

   :param node: the node to be added. """
      branch_value: Any = branch.value if self.key is None else self.key(branch.value)
      node_value: Any = node.value if self.key is None else self.key(node.value)
      if node_value < branch_value:
         if branch.left is None:
            branch.left = node
            self.size += 1
         else:
            self.add_to_branch(branch.left, node)
      elif node_value > branch_value:
         if branch.right is None:
            branch.right = node
            self.size += 1
         else:
            self.add_to_branch(branch.right, node)


   def remove(self, value: Any) -> bool:
      if self.root is None:
         return False

      root_value: Any = self.root.value if self.key is None else self.key(self.root.value)
      cmp_value: Any = value if self.key is None else self.key(value)
      cmp: int = (root_value > cmp_value) - (root_value < cmp_value)
      if cmp == 0:
         if self.root.left is None:
            self.root = self.root.right
         elif self.root.right is None:
            self.root = self.root.left
         else:
            tmp: Node = self.root.right
            self.root = self.root.left
            self.add_to_branch(self.root, tmp)
            self.size -= 1
         self.size -= 1
         return True
      return self.remove_from_branch(self.root, value, cmp);


   def remove_from_branch(self, parent_branch: Node, value: Any, parentCmp: int) -> bool:
      """ Removes a value from a sub-tree.

      :param parent_branch the sub-tree from which the value will be removed.

      :param value: the value to be removed.

      :param parentCmp: comparison value between the sub-tree root and the value. """

      branch: Node = parent_branch.left if parentCmp > 0 else parent_branch.right

      if branch is None:
         return False
      branch_value: Any = branch.value if self.key is None else self.key(branch.value)
      cmp_value: Any = value if self.key is None else self.key(value)
      cmp: int = (branch_value > cmp_value) - (branch_value < cmp_value)
      if cmp == 0:
         newRoot: Node
         if branch.left is None:
            newRoot = branch.right
         elif branch.right is None:
            newRoot = branch.left
         else:
            tmp: Node = branch.right
            newRoot = branch.left
            self.add_to_branch(newRoot, tmp)
            self.size -= 1
         if parentCmp > 0:
            parent_branch.left = newRoot
         else:
            parent_branch.right = newRoot
         self.size -= 1
         return True
      return self.remove_from_branch(branch, value, cmp);


