

"""simple docstring"""




from __future__ import annotations

import unittest
from collections.abc import Iterator





class 			__UpperCamelCase :


		def __init__(self :		int     ,     __SCREAMING_SNAKE_CASE :		Optional[Any]     ,     __SCREAMING_SNAKE_CASE :		Dict):
							A			=					label
							A			=					parent
							A			=					None
							A			=					None





class 			__UpperCamelCase :


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


		def 					SCREAMING_SNAKE_CASE__   (self :		Optional[int]):
							A			=					None


		def 					SCREAMING_SNAKE_CASE__   (self :		Any):
							return self.root is None


		def 					SCREAMING_SNAKE_CASE__   (self :		List[str]     ,     __SCREAMING_SNAKE_CASE :		Any):
							A			=					self._put(self.root     ,     A_)


		def 					SCREAMING_SNAKE_CASE__   (self :		List[str]     ,     __SCREAMING_SNAKE_CASE :		Optional[int]     ,     __SCREAMING_SNAKE_CASE :		Optional[Any]     ,     __SCREAMING_SNAKE_CASE :		List[Any] = None):


							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 :		str     ,     __SCREAMING_SNAKE_CASE :		Dict):
							return self._search(self.root     ,     A_)


		def 					SCREAMING_SNAKE_CASE__   (self :		List[str]     ,     __SCREAMING_SNAKE_CASE :		int     ,     __SCREAMING_SNAKE_CASE :		int):


							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[int]     ,     __SCREAMING_SNAKE_CASE :		int):
							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 :		Optional[Any]     ,     __SCREAMING_SNAKE_CASE :		Union[str, Any]     ,     __SCREAMING_SNAKE_CASE :		Dict):


							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 :		List[str]     ,     __SCREAMING_SNAKE_CASE :		Any):


							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 :		int     ,     __SCREAMING_SNAKE_CASE :		List[Any]):


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


		def 					SCREAMING_SNAKE_CASE__   (self :		Optional[int]):


							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 :		List[Any]):


							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 :		List[Any]):
							return self._inorder_traversal(self.root)


		def 					SCREAMING_SNAKE_CASE__   (self :		Dict     ,     __SCREAMING_SNAKE_CASE :		Tuple):


							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 :		str):
							return self._preorder_traversal(self.root)


		def 					SCREAMING_SNAKE_CASE__   (self :		Optional[int]     ,     __SCREAMING_SNAKE_CASE :		Any):


							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__   ():
							A			=					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 :		int):
							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(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(A_):  # noqa: B017
												t.put(1)


		def 					SCREAMING_SNAKE_CASE__   (self :		Dict):
							A			=					self._get_binary_search_tree()

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

							A			=					t.search(1_3)
							assert node.label == 1_3

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


		def 					SCREAMING_SNAKE_CASE__   (self :		Dict):
							A			=					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 :		Dict):
							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 :		Optional[Any]):
							A			=					self._get_binary_search_tree()
							t.empty()
							assert t.root is None


		def 					SCREAMING_SNAKE_CASE__   (self :		List[str]):
							A			=					self._get_binary_search_tree()
							assert not t.is_empty()

							t.empty()
							assert t.is_empty()


		def 					SCREAMING_SNAKE_CASE__   (self :		Optional[Any]):
							A			=					self._get_binary_search_tree()

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


		def 					SCREAMING_SNAKE_CASE__   (self :		str):
							A			=					self._get_binary_search_tree()

							assert t.get_max_label() == 1_4

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


		def 					SCREAMING_SNAKE_CASE__   (self :		Tuple):
							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 :		Any):
							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, 1_0, 1_3, 1_4]


		def 					SCREAMING_SNAKE_CASE__   (self :		List[Any]):
							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, 1_0, 1_4, 1_3]

def    __SCREAMING_SNAKE_CASE						(						):
					"""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      )

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

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

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

					# 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:"			,							lowercase__      )

					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

class  a     :


						def __init__(				self  ,    A_		):







										'''simple docstring'''


										_UpperCAmelCase				:						List[Any]       						=			vertices
										_UpperCAmelCase				:						List[str]       						=			[[0] * vertices for _ in range(A_		)]


						def 				_UpperCAmelCase (				self  ,    A_		):







										'''simple docstring'''


										print("Vertex \t Distance from Source"		)
										for vertex in range(self.vertices		):
														print(A_  ,    "\t\t"  ,    distances_from_source[vertex]		)


						def 				_UpperCAmelCase (				self  ,    A_  ,    A_		):







										'''simple docstring'''


										_UpperCAmelCase				:						Tuple       						=			1e7
										_UpperCAmelCase				:						Any       						=			0

										# Search not nearest vertex not in the shortest path tree
										for vertex in range(self.vertices		):
														if distances_from_source[vertex] < minimum and visited[vertex] is False:
																		_UpperCAmelCase				:						List[Any]       						=			distances_from_source[vertex]
																		_UpperCAmelCase				:						Tuple       						=			vertex
										return min_index





						def 				_UpperCAmelCase (				self  ,    A_		):







										'''simple docstring'''


										_UpperCAmelCase				:						Union[str, Any]       						=			[int(1e7		)] * self.vertices  # distances from the source
										_UpperCAmelCase				:						Optional[Any]       						=			0
										_UpperCAmelCase				:						List[str]       						=			[False] * self.vertices

										for _ in range(self.vertices		):
														_UpperCAmelCase				:						str       						=			self.minimum_distance(A_  ,    A_		)
														_UpperCAmelCase				:						str       						=			True

														# Update dist value of the adjacent vertices
														# of the picked vertex only if the current
														# distance is greater than new distance and
														# the vertex in not in the shortest path tree
														for v in range(self.vertices		):
																		if (
																		    self.graph[u][v] > 0
																		    and visited[v] is False
																		    and distances[v] > distances[u] + self.graph[u][v]
																		):
																						_UpperCAmelCase				:						str       						=			distances[u] + self.graph[u][v]

										self.print_solution(A_		)


if __name__ == "__main__":
					SCREAMING_SNAKE_CASE_						=					Graph(9)
					SCREAMING_SNAKE_CASE_						=					[
					    [0, 4, 0, 0, 0, 0, 0, 8, 0],
					    [4, 0, 8, 0, 0, 0, 0, 11, 0],
					    [0, 8, 0, 7, 0, 4, 0, 0, 2],
					    [0, 0, 7, 0, 9, 14, 0, 0, 0],
					    [0, 0, 0, 9, 0, 10, 0, 0, 0],
					    [0, 0, 4, 14, 10, 0, 2, 0, 0],
					    [0, 0, 0, 0, 0, 2, 0, 1, 6],
					    [8, 11, 0, 0, 0, 0, 1, 0, 7],
					    [0, 0, 2, 0, 0, 0, 6, 7, 0],
					]
					graph.dijkstra(0)


