




from __future__ import annotations

import unittest
from collections.abc import Iterator

class   UpperCAmelCase    :






   def __init__(						self :							int    ,       UpperCamelCase_ :							int    ,       UpperCamelCase_ :							Node | None  )->      None:
     _lowercase:			Union[str, Any]      =     label
     _lowercase:			int      =     parent
     _lowercase:			Node | None      =     None
     _lowercase:			Node | None      =     None

class   UpperCAmelCase    :






   def __init__(						self :							List[str]  )->      None:
     _lowercase:			Node | None      =     None






   def 			_a    (						self :							str  )->      None:
     _lowercase:			List[Any]      =     None






   def 			_a    (						self :							Optional[Any]  )->      bool:
     return self.root is None






   def 			_a    (						self :							Any    ,       UpperCamelCase_ :							int  )->      None:
     _lowercase:			List[Any]      =     self._put(self.root    ,       UpperCamelCase_  )






   def 			_a    (						self :							List[Any]    ,       UpperCamelCase_ :							Node | None    ,       UpperCamelCase_ :							int    ,       UpperCamelCase_ :							Node | None = None  )->      Node:
     if node is None:
       _lowercase:			Tuple      =     Node(UpperCamelCase_    ,       UpperCamelCase_  )
     else:
       if label < node.label:
         _lowercase:			List[str]      =     self._put(node.left    ,       UpperCamelCase_    ,       UpperCamelCase_  )
       elif label > node.label:
         _lowercase:			Optional[Any]      =     self._put(node.right    ,       UpperCamelCase_    ,       UpperCamelCase_  )
       else:
         _lowercase:			str      =     f'Node with label {label} already exists'
         raise Exception(UpperCamelCase_  )

     return node






   def 			_a    (						self :							List[str]    ,       UpperCamelCase_ :							int  )->      Node:
     return self._search(self.root    ,       UpperCamelCase_  )






   def 			_a    (						self :							List[str]    ,       UpperCamelCase_ :							Node | None    ,       UpperCamelCase_ :							int  )->      Node:
     if node is None:
       _lowercase:			int      =     f'Node with label {label} does not exist'
       raise Exception(UpperCamelCase_  )
     else:
       if label < node.label:
         _lowercase:			Tuple      =     self._search(node.left    ,       UpperCamelCase_  )
       elif label > node.label:
         _lowercase:			List[Any]      =     self._search(node.right    ,       UpperCamelCase_  )

     return node






   def 			_a    (						self :							str    ,       UpperCamelCase_ :							int  )->      None:
     _lowercase:			List[str]      =     self.search(UpperCamelCase_  )
     if node.right and node.left:
       _lowercase:			int      =     self._get_lowest_node(node.right  )
       _lowercase:			List[Any]      =     node.left
       _lowercase:			str      =     node.right
       _lowercase:			Optional[int]      =     lowest_node
       if node.right:
         _lowercase:			Tuple      =     lowest_node
       self._reassign_nodes(UpperCamelCase_    ,       UpperCamelCase_  )
     elif not node.right and node.left:
       self._reassign_nodes(UpperCamelCase_    ,       node.left  )
     elif node.right and not node.left:
       self._reassign_nodes(UpperCamelCase_    ,       node.right  )
     else:
       self._reassign_nodes(UpperCamelCase_    ,       UpperCamelCase_  )






   def 			_a    (						self :							Tuple    ,       UpperCamelCase_ :							Node    ,       UpperCamelCase_ :							Node | None  )->      None:
     if new_children:
       _lowercase:			Tuple      =     node.parent

     if node.parent:
       if node.parent.right == node:
         _lowercase:			Optional[int]      =     new_children
       else:
         _lowercase:			Dict      =     new_children
     else:
       _lowercase:			Tuple      =     new_children






   def 			_a    (						self :							List[Any]    ,       UpperCamelCase_ :							Node  )->      Node:
     if node.left:
       _lowercase:			Tuple      =     self._get_lowest_node(node.left  )
     else:
       _lowercase:			Union[str, Any]      =     node
       self._reassign_nodes(UpperCamelCase_    ,       node.right  )

     return lowest_node






   def 			_a    (						self :							str    ,       UpperCamelCase_ :							int  )->      bool:
     try:
       self.search(UpperCamelCase_  )
       return True
     except Exception:
       return False






   def 			_a    (						self :							Dict  )->      int:
     if self.root is None:
       raise Exception('Binary search tree is empty'  )

     _lowercase:			Optional[int]      =     self.root
     while node.right is not None:
       _lowercase:			str      =     node.right

     return node.label






   def 			_a    (						self :							Union[str, Any]  )->      int:
     if self.root is None:
       raise Exception('Binary search tree is empty'  )

     _lowercase:			Dict      =     self.root
     while node.left is not None:
       _lowercase:			Union[str, Any]      =     node.left

     return node.label






   def 			_a    (						self :							List[str]  )->      Iterator[Node]:
     return self._inorder_traversal(self.root  )






   def 			_a    (						self :							Union[str, Any]    ,       UpperCamelCase_ :							Node | None  )->      Iterator[Node]:
     if node is not None:
       yield from self._inorder_traversal(node.left  )
       yield node
       yield from self._inorder_traversal(node.right  )






   def 			_a    (						self :							Optional[Any]  )->      Iterator[Node]:
     return self._preorder_traversal(self.root  )






   def 			_a    (						self :							List[str]    ,       UpperCamelCase_ :							Node | None  )->      Iterator[Node]:
     if node is not None:
       yield node
       yield from self._preorder_traversal(node.left  )
       yield from self._preorder_traversal(node.right  )

class   UpperCAmelCase    (      unittest.TestCase ):






   @staticmethod
   def 			_a    (						)->      BinarySearchTree:
     _lowercase:			Dict      =     BinarySearchTree()
     t.put(8  )
     t.put(3  )
     t.put(6  )
     t.put(1  )
     t.put(10  )
     t.put(14  )
     t.put(13  )
     t.put(4  )
     t.put(7  )
     t.put(5  )

     return t






   def 			_a    (						self :							Optional[Any]  )->      None:
     _lowercase:			Tuple      =     BinarySearchTree()
     assert t.is_empty()

     t.put(8  )
     assert t.root is not None
     assert t.root.parent is None
     assert t.root.label == 8

     t.put(10  )
     assert t.root.right is not None
     assert t.root.right.parent == t.root
     assert t.root.right.label == 10

     t.put(3  )
     assert t.root.left is not None
     assert t.root.left.parent == t.root
     assert t.root.left.label == 3

     t.put(6  )
     assert t.root.left.right is not None
     assert t.root.left.right.parent == t.root.left
     assert t.root.left.right.label == 6

     t.put(1  )
     assert t.root.left.left is not None
     assert t.root.left.left.parent == t.root.left
     assert t.root.left.left.label == 1

     with self.assertRaises(UpperCamelCase_  ):  # noqa: B017
       t.put(1  )






   def 			_a    (						self :							Dict  )->      None:
     _lowercase:			List[str]      =     self._get_binary_search_tree()

     _lowercase:			Optional[int]      =     t.search(6  )
     assert node.label == 6

     _lowercase:			Optional[int]      =     t.search(13  )
     assert node.label == 13

     with self.assertRaises(UpperCamelCase_  ):  # noqa: B017
       t.search(2  )






   def 			_a    (						self :							List[Any]  )->      None:
     _lowercase:			Dict      =     self._get_binary_search_tree()

     t.remove(13  )
     assert t.root is not None
     assert t.root.right is not None
     assert t.root.right.right is not None
     assert t.root.right.right.right is None
     assert t.root.right.right.left is None

     t.remove(7  )
     assert t.root.left is not None
     assert t.root.left.right is not None
     assert t.root.left.right.left is not None
     assert t.root.left.right.right is None
     assert t.root.left.right.left.label == 4

     t.remove(6  )
     assert t.root.left.left is not None
     assert t.root.left.right.right is not None
     assert t.root.left.left.label == 1
     assert t.root.left.right.label == 4
     assert t.root.left.right.right.label == 5
     assert t.root.left.right.left is None
     assert t.root.left.left.parent == t.root.left
     assert t.root.left.right.parent == t.root.left

     t.remove(3  )
     assert t.root is not None
     assert t.root.left.label == 4
     assert t.root.left.right.label == 5
     assert t.root.left.left.label == 1
     assert t.root.left.parent == t.root
     assert t.root.left.left.parent == t.root.left
     assert t.root.left.right.parent == t.root.left

     t.remove(4  )
     assert t.root.left is not None
     assert t.root.left.left is not None
     assert t.root.left.label == 5
     assert t.root.left.right is None
     assert t.root.left.left.label == 1
     assert t.root.left.parent == t.root
     assert t.root.left.left.parent == t.root.left






   def 			_a    (						self :							Dict  )->      None:
     _lowercase:			Union[str, Any]      =     self._get_binary_search_tree()

     t.remove(3  )
     assert t.root is not None
     assert t.root.left is not None
     assert t.root.left.left is not None
     assert t.root.left.right is not None
     assert t.root.left.right.left is not None
     assert t.root.left.right.right is not None
     assert t.root.left.label == 4
     assert t.root.left.right.label == 6
     assert t.root.left.left.label == 1
     assert t.root.left.right.right.label == 7
     assert t.root.left.right.left.label == 5
     assert t.root.left.parent == t.root
     assert t.root.left.right.parent == t.root.left
     assert t.root.left.left.parent == t.root.left
     assert t.root.left.right.left.parent == t.root.left.right






   def 			_a    (						self :							int  )->      None:
     _lowercase:			Union[str, Any]      =     self._get_binary_search_tree()
     t.empty()
     assert t.root is None






   def 			_a    (						self :							Union[str, Any]  )->      None:
     _lowercase:			int      =     self._get_binary_search_tree()
     assert not t.is_empty()

     t.empty()
     assert t.is_empty()






   def 			_a    (						self :							Tuple  )->      None:
     _lowercase:			Tuple      =     self._get_binary_search_tree()

     assert t.exists(6  )
     assert not t.exists(-1  )






   def 			_a    (						self :							str  )->      None:
     _lowercase:			int      =     self._get_binary_search_tree()

     assert t.get_max_label() == 14

     t.empty()
     with self.assertRaises(UpperCamelCase_  ):  # noqa: B017
       t.get_max_label()






   def 			_a    (						self :							Union[str, Any]  )->      None:
     _lowercase:			Tuple      =     self._get_binary_search_tree()

     assert t.get_min_label() == 1

     t.empty()
     with self.assertRaises(UpperCamelCase_  ):  # noqa: B017
       t.get_min_label()






   def 			_a    (						self :							str  )->      None:
     _lowercase:			List[str]      =     self._get_binary_search_tree()

     _lowercase:			List[Any]      =     [i.label for i in t.inorder_traversal()]
     assert inorder_traversal_nodes == [1, 3, 4, 5, 6, 7, 8, 10, 13, 14]






   def 			_a    (						self :							Any  )->      None:
     _lowercase:			Tuple      =     self._get_binary_search_tree()

     _lowercase:			Any      =     [i.label for i in t.preorder_traversal()]
     assert preorder_traversal_nodes == [8, 3, 1, 6, 4, 5, 7, 10, 14, 13]


def 		_lowerCamelCase					(       )      ->		None:





  """simple docstring"""





  _lowercase:			Optional[Any]      =     BinarySearchTree()
  t.put(8				)
  t.put(3				)
  t.put(6				)
  t.put(1				)
  t.put(10				)
  t.put(14				)
  t.put(13				)
  t.put(4				)
  t.put(7				)
  t.put(5				)

  print(
      '\n            8\n           / \\\n          3   10\n         / \\    \\\n        1   6    14\n           / \\   /\n          4   7 13\n           \\\n            5\n        '				)

  print('Label 6 exists:'       ,  t.exists(6				)				)
  print('Label 13 exists:'       ,  t.exists(13				)				)
  print('Label -1 exists:'       ,  t.exists(-1				)				)
  print('Label 12 exists:'       ,  t.exists(12				)				)

  # Prints all the elements of the list in inorder traversal
  _lowercase:			List[str]      =     [i.label for i in t.inorder_traversal()]
  print('Inorder traversal:'       ,  UpperCamelCase				)

  # Prints all the elements of the list in preorder traversal
  _lowercase:			List[Any]      =     [i.label for i in t.preorder_traversal()]
  print('Preorder traversal:'       ,  UpperCamelCase				)

  print('Max. label:'       ,  t.get_max_label()				)
  print('Min. label:'       ,  t.get_min_label()				)

  # Delete elements
  print('\nDeleting elements 13, 10, 8, 3, 6, 14'				)
  print(
      '\n          4\n         / \\\n        1   7\n             \\\n              5\n        '				)
  t.remove(13				)
  t.remove(10				)
  t.remove(8				)
  t.remove(3				)
  t.remove(6				)
  t.remove(14				)

  # Prints all the elements of the list in inorder traversal after delete
  _lowercase:			Optional[Any]      =     [i.label for i in t.inorder_traversal()]
  print('Inorder traversal after delete:'       ,  UpperCamelCase				)

  # Prints all the elements of the list in preorder traversal after delete
  _lowercase:			Tuple      =     [i.label for i in t.preorder_traversal()]
  print('Preorder traversal after delete:'       ,  UpperCamelCase				)

  print('Max. label:'       ,  t.get_max_label()				)
  print('Min. label:'       ,  t.get_min_label()				)


if __name__ == "__main__":
   binary_search_tree_example()






from math import sqrt


def 		_lowerCamelCase					(       UpperCamelCase				)      ->		list[int]:





  """simple docstring"""





  _lowercase:			Dict      =     [1]
  for i in range(2       ,  int(sqrt(UpperCamelCase				)				) + 1       ,  1				):
    if number % i == 0:
      values.append(UpperCamelCase				)
      if int(number // i				) != i:
        values.append(int(number // i				)				)
  return sorted(UpperCamelCase				)


def 		_lowerCamelCase					(       UpperCamelCase				)      ->		bool:





  """simple docstring"""





  return sum(factors(UpperCamelCase				)				) > n


def 		_lowerCamelCase					(       UpperCamelCase				)      ->		bool:





  """simple docstring"""





  _lowercase:			Dict      =     factors(UpperCamelCase				)
  _lowercase:			int      =     len(UpperCamelCase				)
  _lowercase:			Optional[int]      =     [[0 for i in range(number + 1				)] for j in range(r + 1				)]
  for i in range(r + 1				):
    _lowercase:			List[Any]      =     True

  for i in range(1       ,  number + 1				):
    _lowercase:			Optional[int]      =     False

  for i in range(1       ,  r + 1				):
    for j in range(1       ,  number + 1				):
      if j < values[i - 1]:
        _lowercase:			Optional[int]      =     subset[i - 1][j]
      else:
        _lowercase:			Optional[Any]      =     subset[i - 1][j] or subset[i - 1][j - values[i - 1]]

  return subset[r][number] != 0


def 		_lowerCamelCase					(       UpperCamelCase				)      ->		bool:





  """simple docstring"""





  return abundant(UpperCamelCase				) and not semi_perfect(UpperCamelCase				)


if __name__ == "__main__":
   import doctest

   doctest.testmod(verbose=True)
   for number in (69, 70, 71):
      print(f'''{number} is {'' if weird(number) else 'not '}weird.''')
