



'''simple docstring'''

from __future__ import annotations

import unittest
from collections.abc import Iterator



class 		lowerCamelCase__   :




					'''simple docstring'''



					def __init__(	self					:						Tuple  ,	UpperCamelCase_					:						Union[str, Any]  ,	UpperCamelCase_					:						Optional[Any]       )	->							Optional[int]:



						'''simple docstring'''





						_lowercase       :							List[Any]  	=		label
						_lowercase       :							List[str]  	=		parent
						_lowercase       :							int  	=		None
						_lowercase       :							str  	=		None






class 		lowerCamelCase__   :




					'''simple docstring'''



					def __init__(	self					:						Dict       )	->							Union[str, Any]:



						'''simple docstring'''





						_lowercase       :							Tuple  	=		None




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



						'''simple docstring'''





						_lowercase       :							Tuple  	=		None




					def     __UpperCAmelCase  (	self					:						List[Any]       )	->							List[Any]:



						'''simple docstring'''





						return self.root is None




					def     __UpperCAmelCase  (	self					:						int  ,	UpperCamelCase_					:						Any       )	->							Union[str, Any]:



						'''simple docstring'''





						_lowercase       :							Dict  	=		self._put(self.root  ,	a_       )




					def     __UpperCAmelCase  (	self					:						Tuple  ,	UpperCamelCase_					:						Optional[int]  ,	UpperCamelCase_					:						Tuple  ,	UpperCamelCase_					:						Tuple = None       )	->							Any:



						'''simple docstring'''





						if node is None:
							_lowercase       :							List[str]  	=		Node(a_  ,	a_       )
						else:
							if label < node.label:
								_lowercase       :							Dict  	=		self._put(node.left  ,	a_  ,	a_       )
							elif label > node.label:
								_lowercase       :							Tuple  	=		self._put(node.right  ,	a_  ,	a_       )
							else:
								_lowercase       :							Any  	=		F'''Node with label {label} already exists'''
								raise Exception(a_       )

						return node




					def     __UpperCAmelCase  (	self					:						Optional[Any]  ,	UpperCamelCase_					:						Union[str, Any]       )	->							Dict:



						'''simple docstring'''





						return self._search(self.root  ,	a_       )




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



						'''simple docstring'''





						if node is None:
							_lowercase       :							List[Any]  	=		F'''Node with label {label} does not exist'''
							raise Exception(a_       )
						else:
							if label < node.label:
								_lowercase       :							Union[str, Any]  	=		self._search(node.left  ,	a_       )
							elif label > node.label:
								_lowercase       :							str  	=		self._search(node.right  ,	a_       )

						return node




					def     __UpperCAmelCase  (	self					:						Dict  ,	UpperCamelCase_					:						Union[str, Any]       )	->							List[str]:



						'''simple docstring'''





						_lowercase       :							List[str]  	=		self.search(a_       )
						if node.right and node.left:
							_lowercase       :							Tuple  	=		self._get_lowest_node(node.right       )
							_lowercase       :							int  	=		node.left
							_lowercase       :							List[str]  	=		node.right
							_lowercase       :							Optional[int]  	=		lowest_node
							if node.right:
								_lowercase       :							Any  	=		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     __UpperCAmelCase  (	self					:						Union[str, Any]  ,	UpperCamelCase_					:						Any  ,	UpperCamelCase_					:						int       )	->							List[Any]:



						'''simple docstring'''





						if new_children:
							_lowercase       :							Union[str, Any]  	=		node.parent

						if node.parent:
							if node.parent.right == node:
								_lowercase       :							Dict  	=		new_children
							else:
								_lowercase       :							str  	=		new_children
						else:
							_lowercase       :							List[Any]  	=		new_children




					def     __UpperCAmelCase  (	self					:						Any  ,	UpperCamelCase_					:						Any       )	->							Optional[Any]:



						'''simple docstring'''





						if node.left:
							_lowercase       :							Tuple  	=		self._get_lowest_node(node.left       )
						else:
							_lowercase       :							List[Any]  	=		node
							self._reassign_nodes(a_  ,	node.right       )

						return lowest_node




					def     __UpperCAmelCase  (	self					:						Tuple  ,	UpperCamelCase_					:						Any       )	->							List[Any]:



						'''simple docstring'''





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




					def     __UpperCAmelCase  (	self					:						Dict       )	->							Tuple:



						'''simple docstring'''





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

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

						return node.label




					def     __UpperCAmelCase  (	self					:						str       )	->							Any:



						'''simple docstring'''





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

						_lowercase       :							Union[str, Any]  	=		self.root
						while node.left is not None:
							_lowercase       :							Optional[int]  	=		node.left

						return node.label




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



						'''simple docstring'''





						return self._inorder_traversal(self.root       )




					def     __UpperCAmelCase  (	self					:						Optional[Any]  ,	UpperCamelCase_					:						Tuple       )	->							Any:



						'''simple docstring'''





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




					def     __UpperCAmelCase  (	self					:						int       )	->							Tuple:



						'''simple docstring'''





						return self._preorder_traversal(self.root       )




					def     __UpperCAmelCase  (	self					:						int  ,	UpperCamelCase_					:						Dict       )	->							Union[str, Any]:



						'''simple docstring'''





						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  ):




					'''simple docstring'''



					@staticmethod
					def     __UpperCAmelCase  (	)	->							Optional[Any]:



						'''simple docstring'''





						_lowercase       :							Dict  	=		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     __UpperCAmelCase  (	self					:						str       )	->							str:



						'''simple docstring'''





						_lowercase       :							List[str]  	=		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     __UpperCAmelCase  (	self					:						Optional[Any]       )	->							List[Any]:



						'''simple docstring'''





						_lowercase       :							List[str]  	=		self._get_binary_search_tree()

						_lowercase       :							Tuple  	=		t.search(6       )
						assert node.label == 6

						_lowercase       :							List[str]  	=		t.search(13       )
						assert node.label == 13

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




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



						'''simple docstring'''





						_lowercase       :							List[str]  	=		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     __UpperCAmelCase  (	self					:						Union[str, Any]       )	->							Any:



						'''simple docstring'''





						_lowercase       :							Tuple  	=		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     __UpperCAmelCase  (	self					:						str       )	->							List[Any]:



						'''simple docstring'''





						_lowercase       :							List[str]  	=		self._get_binary_search_tree()
						t.empty()
						assert t.root is None




					def     __UpperCAmelCase  (	self					:						Any       )	->							str:



						'''simple docstring'''





						_lowercase       :							Optional[int]  	=		self._get_binary_search_tree()
						assert not t.is_empty()

						t.empty()
						assert t.is_empty()




					def     __UpperCAmelCase  (	self					:						Union[str, Any]       )	->							Tuple:



						'''simple docstring'''





						_lowercase       :							str  	=		self._get_binary_search_tree()

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




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



						'''simple docstring'''





						_lowercase       :							List[Any]  	=		self._get_binary_search_tree()

						assert t.get_max_label() == 14

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




					def     __UpperCAmelCase  (	self					:						List[Any]       )	->							Optional[Any]:



						'''simple docstring'''





						_lowercase       :							str  	=		self._get_binary_search_tree()

						assert t.get_min_label() == 1

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




					def     __UpperCAmelCase  (	self					:						List[str]       )	->							List[str]:



						'''simple docstring'''





						_lowercase       :							Optional[Any]  	=		self._get_binary_search_tree()

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




					def     __UpperCAmelCase  (	self					:						List[str]       )	->							Optional[Any]:



						'''simple docstring'''





						_lowercase       :							Any  	=		self._get_binary_search_tree()

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







def     __UpperCamelCase					(				)			->      Tuple:
	_lowercase       :							List[str]  	=		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
	_lowercase       :							str  	=		[i.label for i in t.inorder_traversal()]
	print('Inorder traversal:',					__a       )

	# Prints all the elements of the list in preorder traversal
	_lowercase       :							List[Any]  	=		[i.label for i in t.preorder_traversal()]
	print('Preorder traversal:',					__a       )

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

	# Prints all the elements of the list in preorder traversal after delete
	_lowercase       :							Optional[Any]  	=		[i.label for i in t.preorder_traversal()]
	print('Preorder traversal after delete:',					__a       )

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


if __name__ == "__main__":
		binary_search_tree_example()





from collections import defaultdict

def       A_   (						__a  :					str		):

				"""simple docstring"""
				a__					   =		defaultdict(__a		)
				# Creating a dictionary containing count of each word
				for word in sentence.split():
								occurrence[word] += 1
				return occurrence


if __name__ == "__main__":
	for word, count in word_occurrence("""INPUT STRING""").items():
		print(f"""{word}: {count}""")

