




from __future__ import annotations

import unittest
from collections.abc import Iterator







class 		__UpperCAmelCase:





     """simple docstring"""



     def __init__(   self			:							List[str]    ,					A			:							int    ,					A			:							Node | None     )      ->      None:






         """simple docstring"""
         a__  			=							label
         a__  			=							parent
         a__  			=							None
         a__  			=							None







class 		__UpperCAmelCase:





     """simple docstring"""



     def __init__(   self			:							List[Any]     )      ->      None:






         """simple docstring"""
         a__  			=							None

     def 					__SCREAMING_SNAKE_CASE		(   self			:							List[Any]     )      ->      None:






         """simple docstring"""
         a__  			=							None

     def 					__SCREAMING_SNAKE_CASE		(   self			:							List[Any]     )      ->      bool:






         """simple docstring"""
         return self.root is None

     def 					__SCREAMING_SNAKE_CASE		(   self			:							int    ,					A			:							int     )      ->      None:






         """simple docstring"""
         a__  			=							self._put(self.root    ,					A     )

     def 					__SCREAMING_SNAKE_CASE		(   self			:							List[Any]    ,					A			:							Node | None    ,					A			:							int    ,					A			:							Node | None = None     )      ->      Node:






         """simple docstring"""
         if node is None:
             a__  			=							Node(A    ,					A     )
         else:
             if label < node.label:
                 a__  			=							self._put(node.left    ,					A    ,					A     )
             elif label > node.label:
                 a__  			=							self._put(node.right    ,					A    ,					A     )
             else:
                 a__  			=							f"""Node with label {label} already exists"""
                 raise Exception(A     )

         return node

     def 					__SCREAMING_SNAKE_CASE		(   self			:							List[str]    ,					A			:							int     )      ->      Node:






         """simple docstring"""
         return self._search(self.root    ,					A     )

     def 					__SCREAMING_SNAKE_CASE		(   self			:							Union[str, Any]    ,					A			:							Node | None    ,					A			:							int     )      ->      Node:






         """simple docstring"""
         if node is None:
             a__  			=							f"""Node with label {label} does not exist"""
             raise Exception(A     )
         else:
             if label < node.label:
                 a__  			=							self._search(node.left    ,					A     )
             elif label > node.label:
                 a__  			=							self._search(node.right    ,					A     )

         return node

     def 					__SCREAMING_SNAKE_CASE		(   self			:							Optional[Any]    ,					A			:							int     )      ->      None:






         """simple docstring"""
         a__  			=							self.search(A     )
         if node.right and node.left:
             a__  			=							self._get_lowest_node(node.right     )
             a__  			=							node.left
             a__  			=							node.right
             a__  			=							lowest_node
             if node.right:
                 a__  			=							lowest_node
             self._reassign_nodes(A    ,					A     )
         elif not node.right and node.left:
             self._reassign_nodes(A    ,					node.left     )
         elif node.right and not node.left:
             self._reassign_nodes(A    ,					node.right     )
         else:
             self._reassign_nodes(A    ,					A     )

     def 					__SCREAMING_SNAKE_CASE		(   self			:							int    ,					A			:							Node    ,					A			:							Node | None     )      ->      None:






         """simple docstring"""
         if new_children:
             a__  			=							node.parent

         if node.parent:
             if node.parent.right == node:
                 a__  			=							new_children
             else:
                 a__  			=							new_children
         else:
             a__  			=							new_children

     def 					__SCREAMING_SNAKE_CASE		(   self			:							Dict    ,					A			:							Node     )      ->      Node:






         """simple docstring"""
         if node.left:
             a__  			=							self._get_lowest_node(node.left     )
         else:
             a__  			=							node
             self._reassign_nodes(A    ,					node.right     )

         return lowest_node

     def 					__SCREAMING_SNAKE_CASE		(   self			:							Any    ,					A			:							int     )      ->      bool:






         """simple docstring"""
         try:
             self.search(A     )
             return True
         except Exception:
             return False

     def 					__SCREAMING_SNAKE_CASE		(   self			:							str     )      ->      int:






         """simple docstring"""
         if self.root is None:
             raise Exception("""Binary search tree is empty"""     )

         a__  			=							self.root
         while node.right is not None:
             a__  			=							node.right

         return node.label

     def 					__SCREAMING_SNAKE_CASE		(   self			:							Tuple     )      ->      int:






         """simple docstring"""
         if self.root is None:
             raise Exception("""Binary search tree is empty"""     )

         a__  			=							self.root
         while node.left is not None:
             a__  			=							node.left

         return node.label

     def 					__SCREAMING_SNAKE_CASE		(   self			:							Optional[int]     )      ->      Iterator[Node]:






         """simple docstring"""
         return self._inorder_traversal(self.root     )

     def 					__SCREAMING_SNAKE_CASE		(   self			:							Dict    ,					A			:							Node | None     )      ->      Iterator[Node]:






         """simple docstring"""
         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			:							List[Any]     )      ->      Iterator[Node]:






         """simple docstring"""
         return self._preorder_traversal(self.root     )






     def 					__SCREAMING_SNAKE_CASE		(   self			:							Any    ,					A			:							Node | None     )      ->      Iterator[Node]:






         """simple docstring"""
         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			):





     """simple docstring"""



     @staticmethod
     def 					__SCREAMING_SNAKE_CASE		(   )      ->      BinarySearchTree:






         """simple docstring"""
         a__  			=							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 					__SCREAMING_SNAKE_CASE		(   self			:							List[Any]     )      ->      None:






         """simple docstring"""
         a__  			=							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(A     ):  # noqa: B017
             t.put(1     )

     def 					__SCREAMING_SNAKE_CASE		(   self			:							int     )      ->      None:






         """simple docstring"""
         a__  			=							self._get_binary_search_tree()

         a__  			=							t.search(6     )
         assert node.label == 6

         a__  			=							t.search(13     )
         assert node.label == 13

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

     def 					__SCREAMING_SNAKE_CASE		(   self			:							Tuple     )      ->      None:






         """simple docstring"""
         a__  			=							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 					__SCREAMING_SNAKE_CASE		(   self			:							Tuple     )      ->      None:






         """simple docstring"""
         a__  			=							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			:							List[Any]     )      ->      None:






         """simple docstring"""
         a__  			=							self._get_binary_search_tree()
         t.empty()
         assert t.root is None

     def 					__SCREAMING_SNAKE_CASE		(   self			:							List[str]     )      ->      None:






         """simple docstring"""
         a__  			=							self._get_binary_search_tree()
         assert not t.is_empty()

         t.empty()
         assert t.is_empty()

     def 					__SCREAMING_SNAKE_CASE		(   self			:							Dict     )      ->      None:






         """simple docstring"""
         a__  			=							self._get_binary_search_tree()

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

     def 					__SCREAMING_SNAKE_CASE		(   self			:							Tuple     )      ->      None:






         """simple docstring"""
         a__  			=							self._get_binary_search_tree()

         assert t.get_max_label() == 14

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

     def 					__SCREAMING_SNAKE_CASE		(   self			:							Dict     )      ->      None:






         """simple docstring"""
         a__  			=							self._get_binary_search_tree()

         assert t.get_min_label() == 1

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

     def 					__SCREAMING_SNAKE_CASE		(   self			:							Optional[Any]     )      ->      None:






         """simple docstring"""
         a__  			=							self._get_binary_search_tree()

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






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






         """simple docstring"""
         a__  			=							self._get_binary_search_tree()

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






def 							__lowerCAmelCase			():
    a__  			=							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
    a__  			=							[i.label for i in t.inorder_traversal()]
    print("""Inorder traversal:""" ,     UpperCAmelCase_		)

    # Prints all the elements of the list in preorder traversal
    a__  			=							[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
    a__  			=							[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
    a__  			=							[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 __future__ import annotations

import random







class 		__UpperCAmelCase:





     """simple docstring"""



     __UpperCAmelCase						:			Optional[int]							=     6

     def __init__(   self			:							int     )      ->      Optional[Any]:






         """simple docstring"""
         a__  			=							list(range(1    ,					Dice.NUM_SIDES + 1     )     )






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






         """simple docstring"""
         return random.choice(self.sides     )






def 							__lowerCAmelCase			(UpperCAmelCase_ ,     UpperCAmelCase_ = 2		):
    a__  			=							[Dice() for i in range(UpperCAmelCase_		)]
    a__  			=							[0] * (len(UpperCAmelCase_		) * Dice.NUM_SIDES + 1)
    for _ in range(UpperCAmelCase_		):
        count_of_sum[sum(dice.roll() for dice in dices		)] += 1
    a__  			=							[round((count * 100) / num_throws ,     2		) for count in count_of_sum]
    return probability[num_dice:]  # remove probability of sums that never appear


if __name__ == "__main__":
 import doctest

 doctest.testmod()






