




'''simple docstring'''





from __future__ import annotations

import unittest
from collections.abc import Iterator




class 							UpperCAmelCase :


 def __init__(			self       :  Union[str, Any] ,					__lowerCamelCase       :  int ,					__lowerCamelCase       :  Node | None   ):
    UpperCAmelCase__  :int            =			label
    UpperCAmelCase__  :Optional[int]            =			parent
    UpperCAmelCase__  :str            =			None
    UpperCAmelCase__  :Optional[int]            =			None




class 							UpperCAmelCase :


 def __init__(			self       :  Dict   ):
    UpperCAmelCase__  :List[Any]            =			None


 def 					__SCREAMING_SNAKE_CASE				(			self       :  str   ):
    UpperCAmelCase__  :List[Any]            =			None


 def 					__SCREAMING_SNAKE_CASE				(			self       :  Optional[int]   ):
    return self.root is None


 def 					__SCREAMING_SNAKE_CASE				(			self       :  Optional[Any] ,					__lowerCamelCase       :  int   ):
    UpperCAmelCase__  :List[str]            =			self._put(self.root ,					__lowerCamelCase   )


 def 					__SCREAMING_SNAKE_CASE				(			self       :  Optional[Any] ,					__lowerCamelCase       :  Node | None ,					__lowerCamelCase       :  int ,					__lowerCamelCase       :  Node | None = None   ):







    if node is None:
       UpperCAmelCase__  :Any            =			Node(__lowerCamelCase ,					__lowerCamelCase   )
    else:
       if label < node.label:
          UpperCAmelCase__  :Dict            =			self._put(node.left ,					__lowerCamelCase ,					__lowerCamelCase   )
       elif label > node.label:
          UpperCAmelCase__  :Union[str, Any]            =			self._put(node.right ,					__lowerCamelCase ,					__lowerCamelCase   )
       else:
          UpperCAmelCase__  :str            =			f'''Node with label {label} already exists'''
          raise Exception(__lowerCamelCase   )

    return node


 def 					__SCREAMING_SNAKE_CASE				(			self       :  Tuple ,					__lowerCamelCase       :  int   ):
    return self._search(self.root ,					__lowerCamelCase   )


 def 					__SCREAMING_SNAKE_CASE				(			self       :  List[str] ,					__lowerCamelCase       :  Node | None ,					__lowerCamelCase       :  int   ):







    if node is None:
       UpperCAmelCase__  :Dict            =			f'''Node with label {label} does not exist'''
       raise Exception(__lowerCamelCase   )
    else:
       if label < node.label:
          UpperCAmelCase__  :Tuple            =			self._search(node.left ,					__lowerCamelCase   )
       elif label > node.label:
          UpperCAmelCase__  :Union[str, Any]            =			self._search(node.right ,					__lowerCamelCase   )

    return node


 def 					__SCREAMING_SNAKE_CASE				(			self       :  Any ,					__lowerCamelCase       :  int   ):
    UpperCAmelCase__  :str            =			self.search(__lowerCamelCase   )
    if node.right and node.left:
       UpperCAmelCase__  :Union[str, Any]            =			self._get_lowest_node(node.right   )
       UpperCAmelCase__  :Optional[Any]            =			node.left
       UpperCAmelCase__  :List[str]            =			node.right
       UpperCAmelCase__  :List[str]            =			lowest_node
       if node.right:
          UpperCAmelCase__  :int            =			lowest_node
       self._reassign_nodes(__lowerCamelCase ,					__lowerCamelCase   )
    elif not node.right and node.left:
       self._reassign_nodes(__lowerCamelCase ,					node.left   )
    elif node.right and not node.left:
       self._reassign_nodes(__lowerCamelCase ,					node.right   )
    else:
       self._reassign_nodes(__lowerCamelCase ,					__lowerCamelCase   )


 def 					__SCREAMING_SNAKE_CASE				(			self       :  Tuple ,					__lowerCamelCase       :  Node ,					__lowerCamelCase       :  Node | None   ):







    if new_children:
       UpperCAmelCase__  :str            =			node.parent

    if node.parent:
       if node.parent.right == node:
          UpperCAmelCase__  :List[str]            =			new_children
       else:
          UpperCAmelCase__  :Optional[Any]            =			new_children
    else:
       UpperCAmelCase__  :Tuple            =			new_children


 def 					__SCREAMING_SNAKE_CASE				(			self       :  int ,					__lowerCamelCase       :  Node   ):







    if node.left:
       UpperCAmelCase__  :Optional[int]            =			self._get_lowest_node(node.left   )
    else:
       UpperCAmelCase__  :Any            =			node
       self._reassign_nodes(__lowerCamelCase ,					node.right   )

    return lowest_node


 def 					__SCREAMING_SNAKE_CASE				(			self       :  int ,					__lowerCamelCase       :  int   ):







    try:
       self.search(__lowerCamelCase   )
       return True
    except Exception:
       return False


 def 					__SCREAMING_SNAKE_CASE				(			self       :  Union[str, Any]   ):







    if self.root is None:
       raise Exception('''Binary search tree is empty'''   )

    UpperCAmelCase__  :Union[str, Any]            =			self.root
    while node.right is not None:
       UpperCAmelCase__  :int            =			node.right

    return node.label


 def 					__SCREAMING_SNAKE_CASE				(			self       :  Union[str, Any]   ):







    if self.root is None:
       raise Exception('''Binary search tree is empty'''   )

    UpperCAmelCase__  :Tuple            =			self.root
    while node.left is not None:
       UpperCAmelCase__  :str            =			node.left

    return node.label


 def 					__SCREAMING_SNAKE_CASE				(			self       :  List[Any]   ):
    return self._inorder_traversal(self.root   )


 def 					__SCREAMING_SNAKE_CASE				(			self       :  str ,					__lowerCamelCase       :  Node | None   ):







    if node is not None:
       yield from self._inorder_traversal(node.left   )
       yield node
       yield from self._inorder_traversal(node.right   )


 def 					__SCREAMING_SNAKE_CASE				(			self       :  Optional[Any]   ):
    return self._preorder_traversal(self.root   )





 def 					__SCREAMING_SNAKE_CASE				(			self       :  Any ,					__lowerCamelCase       :  Node | None   ):







    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 					__SCREAMING_SNAKE_CASE				(			):
    UpperCAmelCase__  :Dict            =			BinarySearchTree()
    t.put(8   )
    t.put(3   )
    t.put(6   )
    t.put(1   )
    t.put(1_0   )
    t.put(1_4   )
    t.put(1_3   )
    t.put(4   )
    t.put(7   )
    t.put(5   )

    return t


 def 					__SCREAMING_SNAKE_CASE				(			self       :  Dict   ):
    UpperCAmelCase__  :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(1_0   )
    assert t.root.right is not None
    assert t.root.right.parent == t.root
    assert t.root.right.label == 1_0

    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(__lowerCamelCase   ):  # noqa: B017
       t.put(1   )


 def 					__SCREAMING_SNAKE_CASE				(			self       :  Tuple   ):
    UpperCAmelCase__  :Any            =			self._get_binary_search_tree()

    UpperCAmelCase__  :Union[str, Any]            =			t.search(6   )
    assert node.label == 6

    UpperCAmelCase__  :Tuple            =			t.search(1_3   )
    assert node.label == 1_3

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


 def 					__SCREAMING_SNAKE_CASE				(			self       :  Any   ):
    UpperCAmelCase__  :int            =			self._get_binary_search_tree()

    t.remove(1_3   )
    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 					__SCREAMING_SNAKE_CASE				(			self       :  int   ):
    UpperCAmelCase__  :List[str]            =			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 					__SCREAMING_SNAKE_CASE				(			self       :  int   ):
    UpperCAmelCase__  :Tuple            =			self._get_binary_search_tree()
    t.empty()
    assert t.root is None


 def 					__SCREAMING_SNAKE_CASE				(			self       :  str   ):
    UpperCAmelCase__  :List[Any]            =			self._get_binary_search_tree()
    assert not t.is_empty()

    t.empty()
    assert t.is_empty()


 def 					__SCREAMING_SNAKE_CASE				(			self       :  Any   ):
    UpperCAmelCase__  :Union[str, Any]            =			self._get_binary_search_tree()

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


 def 					__SCREAMING_SNAKE_CASE				(			self       :  List[str]   ):
    UpperCAmelCase__  :Dict            =			self._get_binary_search_tree()

    assert t.get_max_label() == 1_4

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


 def 					__SCREAMING_SNAKE_CASE				(			self       :  Optional[int]   ):
    UpperCAmelCase__  :Tuple            =			self._get_binary_search_tree()

    assert t.get_min_label() == 1

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


 def 					__SCREAMING_SNAKE_CASE				(			self       :  Optional[int]   ):
    UpperCAmelCase__  :List[Any]            =			self._get_binary_search_tree()

    UpperCAmelCase__  :Optional[int]            =			[i.label for i in t.inorder_traversal()]
    assert inorder_traversal_nodes == [1, 3, 4, 5, 6, 7, 8, 1_0, 1_3, 1_4]





 def 					__SCREAMING_SNAKE_CASE				(			self       :  List[Any]   ):
    UpperCAmelCase__  :Optional[int]            =			self._get_binary_search_tree()

    UpperCAmelCase__  :Tuple            =			[i.label for i in t.preorder_traversal()]
    assert preorder_traversal_nodes == [8, 3, 1, 6, 4, 5, 7, 1_0, 1_4, 1_3]


def 					a__    (				):
   UpperCAmelCase__  :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(
       '''
            8
           / \\
          3   10
         / \\    \\
        1   6    14
           / \\   /
          4   7 13
           \\
            5
        '''	)

   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
   UpperCAmelCase__  :int            =			[i.label for i in t.inorder_traversal()]
   print('''Inorder traversal:''',      UpperCamelCase_	)

   # Prints all the elements of the list in preorder traversal
   UpperCAmelCase__  :Optional[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(
       '''
          4
         / \\
        1   7
             \\
              5
        '''	)
   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
   UpperCAmelCase__  :int            =			[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
   UpperCAmelCase__  :int            =			[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()







'''simple docstring'''





def 					a__    (				UpperCamelCase_	:			int	):
   UpperCAmelCase__  :str            =			[True for i in range(n + 1	)]
   UpperCAmelCase__  :List[str]            =			[i - 1 for i in range(n + 1	)]
   UpperCAmelCase__  :str            =			[]
   for i in range(2,      n + 1	):
      if is_prime[i]:
         primes.append(UpperCamelCase_	)
      for j in range(0,      len(UpperCamelCase_	)	):
         if i * primes[j] >= n:
            break
         UpperCAmelCase__  :List[str]            =			False

         if i % primes[j] == 0:
            UpperCAmelCase__  :Any            =			totients[i] * primes[j]
            break

         UpperCAmelCase__  :str            =			totients[i] * (primes[j] - 1)

   return totients


if __name__ == "__main__":
    import doctest

    doctest.testmod()



