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

import unittest
from collections.abc import Iterator


class    _lowerCAmelCase						:



							def __init__(      self ,						a_ ,						a_   )							->							None:
								_UpperCAmelCase =						label
								_UpperCAmelCase =						parent
								_UpperCAmelCase =						None
								_UpperCAmelCase =						None





class    _lowerCAmelCase						:



							def __init__(      self   )							->							None:
								_UpperCAmelCase =						None



							def       _a   (      self   )							->							None:
								_UpperCAmelCase =						None



							def       _a   (      self   )							->							bool:
								return self.root is None



							def       _a   (      self ,						a_   )							->							None:
								_UpperCAmelCase =						self._put(self.root ,						a_   )



							def       _a   (      self ,						a_ ,						a_ ,						a_ = None   )							->							Node:
								if node is None:
									_UpperCAmelCase =						Node(a_ ,						a_   )
								else:
									if label < node.label:
										_UpperCAmelCase =						self._put(node.left ,						a_ ,						a_   )
									elif label > node.label:
										_UpperCAmelCase =						self._put(node.right ,						a_ ,						a_   )
									else:
										_UpperCAmelCase =						f"Node with label {label} already exists"
										raise Exception(a_   )

								return node



							def       _a   (      self ,						a_   )							->							Node:
								return self._search(self.root ,						a_   )



							def       _a   (      self ,						a_ ,						a_   )							->							Node:
								if node is None:
									_UpperCAmelCase =						f"Node with label {label} does not exist"
									raise Exception(a_   )
								else:
									if label < node.label:
										_UpperCAmelCase =						self._search(node.left ,						a_   )
									elif label > node.label:
										_UpperCAmelCase =						self._search(node.right ,						a_   )

								return node



							def       _a   (      self ,						a_   )							->							None:
								_UpperCAmelCase =						self.search(a_   )
								if node.right and node.left:
									_UpperCAmelCase =						self._get_lowest_node(node.right   )
									_UpperCAmelCase =						node.left
									_UpperCAmelCase =						node.right
									_UpperCAmelCase =						lowest_node
									if node.right:
										_UpperCAmelCase =						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       _a   (      self ,						a_ ,						a_   )							->							None:
								if new_children:
									_UpperCAmelCase =						node.parent

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



							def       _a   (      self ,						a_   )							->							Node:
								if node.left:
									_UpperCAmelCase =						self._get_lowest_node(node.left   )
								else:
									_UpperCAmelCase =						node
									self._reassign_nodes(a_ ,						node.right   )

								return lowest_node



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



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

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

								return node.label



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

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

								return node.label



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



							def       _a   (      self ,						a_   )							->							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   )							->							Iterator[Node]:
								return self._preorder_traversal(self.root   )



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





class    _lowerCAmelCase						(						unittest.TestCase						):



							@staticmethod
							def       _a   (      )							->							BinarySearchTree:
								_UpperCAmelCase =						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   )							->							None:
								_UpperCAmelCase =						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       _a   (      self   )							->							None:
								_UpperCAmelCase =						self._get_binary_search_tree()

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

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

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



							def       _a   (      self   )							->							None:
								_UpperCAmelCase =						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   )							->							None:
								_UpperCAmelCase =						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   )							->							None:
								_UpperCAmelCase =						self._get_binary_search_tree()
								t.empty()
								assert t.root is None



							def       _a   (      self   )							->							None:
								_UpperCAmelCase =						self._get_binary_search_tree()
								assert not t.is_empty()

								t.empty()
								assert t.is_empty()



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

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



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

								assert t.get_max_label() == 14

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



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

								assert t.get_min_label() == 1

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



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

								_UpperCAmelCase =						[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   )							->							None:
								_UpperCAmelCase =						self._get_binary_search_tree()

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





def     __lowerCamelCase  (		):


	"""simple docstring"""






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

	# Prints all the elements of the list in preorder traversal
	_UpperCAmelCase =						[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
	_UpperCAmelCase =						[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 =						[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     __lowerCamelCase  (		UpperCamelCase__      ):


	"""simple docstring"""






	if not isinstance(UpperCamelCase__				,     UpperCamelCase__      ):
		raise TypeError("recursive_lucas_number accepts only integer arguments."      )
	if n_th_number == 0:
		return 2
	if n_th_number == 1:
		return 1

	return recursive_lucas_number(n_th_number - 1      ) + recursive_lucas_number(
	    n_th_number - 2      )




def     __lowerCamelCase  (		UpperCamelCase__      ):


	"""simple docstring"""






	if not isinstance(UpperCamelCase__				,     UpperCamelCase__      ):
		raise TypeError("dynamic_lucas_number accepts only integer arguments."      )
	_UpperCAmelCase ,      _UpperCAmelCase =						2, 1
	for _ in range(UpperCamelCase__      ):
		_UpperCAmelCase ,      _UpperCAmelCase =						b, a + b
	return a


if __name__ == "__main__":
			from doctest import testmod

			testmod()
			__magic_name__		       =				int(input('''Enter the number of terms in lucas series:\n''').strip())
			print('''Using recursive function to calculate lucas series:''')
			print(''' '''.join(str(recursive_lucas_number(i)) for i in range(n)))
			print('''\nUsing dynamic function to calculate lucas series:''')
			print(''' '''.join(str(dynamic_lucas_number(i)) for i in range(n)))




