


"""simple docstring"""
from __future__ import annotations

import unittest
from collections.abc import Iterator





class   __A  :





							'''simple docstring'''

							def __init__(					self				:   Optional[Any]		,							UpperCAmelCase_				:   int		,							UpperCAmelCase_				:   Node | None							)       ->None:



														"""simple docstring"""



														snake_case_     							=		label
														snake_case_     							=		parent
														snake_case_     							=		None
														snake_case_     							=		None





class   __A  :





							'''simple docstring'''

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



														"""simple docstring"""



														snake_case_     							=		None



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



														"""simple docstring"""



														snake_case_     							=		None



							def 		lowerCAmelCase							(					self				:   int							)       ->bool:



														"""simple docstring"""



														return self.root is None



							def 		lowerCAmelCase							(					self				:   List[str]		,							UpperCAmelCase_				:   int							)       ->None:



														"""simple docstring"""



														snake_case_     							=		self._put(self.root		,							UpperCAmelCase_							)



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



														"""simple docstring"""



														if node is None:
																					snake_case_     							=		Node(UpperCAmelCase_		,							UpperCAmelCase_							)
														else:
																					if label < node.label:
																												snake_case_     							=		self._put(node.left		,							UpperCAmelCase_		,							UpperCAmelCase_							)
																					elif label > node.label:
																												snake_case_     							=		self._put(node.right		,							UpperCAmelCase_		,							UpperCAmelCase_							)
																					else:
																												snake_case_     							=		F"""Node with label {label} already exists"""
																												raise Exception(UpperCAmelCase_							)

														return node



							def 		lowerCAmelCase							(					self				:   Union[str, Any]		,							UpperCAmelCase_				:   int							)       ->Node:



														"""simple docstring"""



														return self._search(self.root		,							UpperCAmelCase_							)



							def 		lowerCAmelCase							(					self				:   Any		,							UpperCAmelCase_				:   Node | None		,							UpperCAmelCase_				:   int							)       ->Node:



														"""simple docstring"""



														if node is None:
																					snake_case_     							=		F"""Node with label {label} does not exist"""
																					raise Exception(UpperCAmelCase_							)
														else:
																					if label < node.label:
																												snake_case_     							=		self._search(node.left		,							UpperCAmelCase_							)
																					elif label > node.label:
																												snake_case_     							=		self._search(node.right		,							UpperCAmelCase_							)

														return node



							def 		lowerCAmelCase							(					self				:   List[Any]		,							UpperCAmelCase_				:   int							)       ->None:



														"""simple docstring"""



														snake_case_     							=		self.search(UpperCAmelCase_							)
														if node.right and node.left:
																					snake_case_     							=		self._get_lowest_node(node.right							)
																					snake_case_     							=		node.left
																					snake_case_     							=		node.right
																					snake_case_     							=		lowest_node
																					if node.right:
																												snake_case_     							=		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 		lowerCAmelCase							(					self				:   Optional[int]		,							UpperCAmelCase_				:   Node		,							UpperCAmelCase_				:   Node | None							)       ->None:



														"""simple docstring"""



														if new_children:
																					snake_case_     							=		node.parent

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



							def 		lowerCAmelCase							(					self				:   List[Any]		,							UpperCAmelCase_				:   Node							)       ->Node:



														"""simple docstring"""



														if node.left:
																					snake_case_     							=		self._get_lowest_node(node.left							)
														else:
																					snake_case_     							=		node
																					self._reassign_nodes(UpperCAmelCase_		,							node.right							)

														return lowest_node



							def 		lowerCAmelCase							(					self				:   Optional[Any]		,							UpperCAmelCase_				:   int							)       ->bool:



														"""simple docstring"""



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



							def 		lowerCAmelCase							(					self				:   List[str]							)       ->int:



														"""simple docstring"""



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

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

														return node.label



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



														"""simple docstring"""



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

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

														return node.label



							def 		lowerCAmelCase							(					self				:   Dict							)       ->Iterator[Node]:



														"""simple docstring"""



														return self._inorder_traversal(self.root							)



							def 		lowerCAmelCase							(					self				:   int		,							UpperCAmelCase_				:   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 		lowerCAmelCase							(					self				:   str							)       ->Iterator[Node]:



														"""simple docstring"""



														return self._preorder_traversal(self.root							)



							def 		lowerCAmelCase							(					self				:   Tuple		,							UpperCAmelCase_				:   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   __A  (unittest.TestCase):





							'''simple docstring'''

							@staticmethod
							def 		lowerCAmelCase							(					)       ->BinarySearchTree:



														"""simple docstring"""



														snake_case_     							=		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 		lowerCAmelCase							(					self				:   Any							)       ->None:



														"""simple docstring"""



														snake_case_     							=		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 		lowerCAmelCase							(					self				:   int							)       ->None:



														"""simple docstring"""



														snake_case_     							=		self._get_binary_search_tree()

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

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

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



							def 		lowerCAmelCase							(					self				:   Any							)       ->None:



														"""simple docstring"""



														snake_case_     							=		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 		lowerCAmelCase							(					self				:   List[Any]							)       ->None:



														"""simple docstring"""



														snake_case_     							=		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 		lowerCAmelCase							(					self				:   Union[str, Any]							)       ->None:



														"""simple docstring"""



														snake_case_     							=		self._get_binary_search_tree()
														t.empty()
														assert t.root is None



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



														"""simple docstring"""



														snake_case_     							=		self._get_binary_search_tree()
														assert not t.is_empty()

														t.empty()
														assert t.is_empty()



							def 		lowerCAmelCase							(					self				:   Tuple							)       ->None:



														"""simple docstring"""



														snake_case_     							=		self._get_binary_search_tree()

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



							def 		lowerCAmelCase							(					self				:   Any							)       ->None:



														"""simple docstring"""



														snake_case_     							=		self._get_binary_search_tree()

														assert t.get_max_label() == 14

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



							def 		lowerCAmelCase							(					self				:   Any							)       ->None:



														"""simple docstring"""



														snake_case_     							=		self._get_binary_search_tree()

														assert t.get_min_label() == 1

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



							def 		lowerCAmelCase							(					self				:   Any							)       ->None:



														"""simple docstring"""



														snake_case_     							=		self._get_binary_search_tree()

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



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



														"""simple docstring"""



														snake_case_     							=		self._get_binary_search_tree()

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







def     _a					(   )     ->					None:
							snake_case_     							=		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
							snake_case_     							=		[i.label for i in t.inorder_traversal()]
							print("""Inorder traversal:"""					,			_SCREAMING_SNAKE_CASE					)

							# Prints all the elements of the list in preorder traversal
							snake_case_     							=		[i.label for i in t.preorder_traversal()]
							print("""Preorder traversal:"""					,			_SCREAMING_SNAKE_CASE					)

							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
							snake_case_     							=		[i.label for i in t.inorder_traversal()]
							print("""Inorder traversal after delete:"""					,			_SCREAMING_SNAKE_CASE					)

							# Prints all the elements of the list in preorder traversal after delete
							snake_case_     							=		[i.label for i in t.preorder_traversal()]
							print("""Preorder traversal after delete:"""					,			_SCREAMING_SNAKE_CASE					)

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


if __name__ == "__main__":
				binary_search_tree_example()







"""simple docstring"""
import doctest

import projectq
from projectq.ops import H, Measure







def     _a					(   _SCREAMING_SNAKE_CASE					)     ->					int:
							snake_case_     							=		quantum_engine.allocate_qubit()
							H | qubit
							Measure | qubit
							return int(_SCREAMING_SNAKE_CASE					)


if __name__ == "__main__":
				doctest.testmod()

				# initialises a new quantum backend
				__SCREAMING_SNAKE_CASE				:     Dict		=     projectq.MainEngine()

				# Generate a list of 10 random numbers
				__SCREAMING_SNAKE_CASE				:     Optional[Any]		=     [get_random_number(quantum_engine) for _ in range(10)]

				# Flushes the quantum engine from memory
				quantum_engine.flush()

				print('Random numbers', random_numbers_list)



