


'''simple docstring'''






from __future__ import annotations

import queue




class 	a__       :





							'''simple docstring'''






							def __init__(	self      ,					lowerCamelCase_     ) ->							Optional[int]:
														lowerCAmelCase__      =			data
														lowerCAmelCase__      =			None
														lowerCAmelCase__      =			None


def       _snake_case     (  )		->					TreeNode:
							print('''\n********Press N to stop entering at any point of time********\n''' )
							lowerCAmelCase__      =			input('''Enter the value of the root node: ''' ).strip().lower()
							lowerCAmelCase__      =			queue.Queue()
							lowerCAmelCase__      =			TreeNode(int(A ) )
							q.put(A )
							while not q.empty():
														lowerCAmelCase__      =			q.get()
														lowerCAmelCase__      =			F"""Enter the left node of {node_found.data}: """
														lowerCAmelCase__      =			input(A ).strip().lower() or '''n'''
														if check == "n":
																					return tree_node
														lowerCAmelCase__      =			TreeNode(int(A ) )
														lowerCAmelCase__      =			left_node
														q.put(A )
														lowerCAmelCase__      =			F"""Enter the right node of {node_found.data}: """
														lowerCAmelCase__      =			input(A ).strip().lower() or '''n'''
														if check == "n":
																					return tree_node
														lowerCAmelCase__      =			TreeNode(int(A ) )
														lowerCAmelCase__      =			right_node
														q.put(A )
							raise


def       _snake_case     (  A )		->					None:
							if not isinstance(A				,					A ) or not node:
														return
							print(node.data				,					end=''',''' )
							pre_order(node.left )
							pre_order(node.right )


def       _snake_case     (  A )		->					None:
							if not isinstance(A				,					A ) or not node:
														return
							in_order(node.left )
							print(node.data				,					end=''',''' )
							in_order(node.right )


def       _snake_case     (  A )		->					None:
							if not isinstance(A				,					A ) or not node:
														return
							post_order(node.left )
							post_order(node.right )
							print(node.data				,					end=''',''' )


def       _snake_case     (  A )		->					None:
							if not isinstance(A				,					A ) or not node:
														return
							lowerCAmelCase__      =			queue.Queue()
							q.put(A )
							while not q.empty():
														lowerCAmelCase__      =			q.get()
														print(node_dequeued.data				,					end=''',''' )
														if node_dequeued.left:
																					q.put(node_dequeued.left )
														if node_dequeued.right:
																					q.put(node_dequeued.right )


def       _snake_case     (  A )		->					None:
							if not isinstance(A				,					A ) or not node:
														return
							lowerCAmelCase__      =			queue.Queue()
							q.put(A )
							while not q.empty():
														lowerCAmelCase__      =			[]
														while not q.empty():
																					lowerCAmelCase__      =			q.get()
																					print(node_dequeued.data				,					end=''',''' )
																					if node_dequeued.left:
																												list_.append(node_dequeued.left )
																					if node_dequeued.right:
																												list_.append(node_dequeued.right )
														print()
														for node in list_:
																					q.put(A )


def       _snake_case     (  A )		->					None:
							if not isinstance(A				,					A ) or not node:
														return
							lowerCAmelCase__      =			[]
							lowerCAmelCase__      =			node
							while n or stack:
														while n:  # start from root node, find its left child
																					print(n.data				,					end=''',''' )
																					stack.append(A )
																					lowerCAmelCase__      =			n.left
														# end of while means current node doesn't have left child
														lowerCAmelCase__      =			stack.pop()
														# start to traverse its right child
														lowerCAmelCase__      =			n.right


def       _snake_case     (  A )		->					None:
							if not isinstance(A				,					A ) or not node:
														return
							lowerCAmelCase__      =			[]
							lowerCAmelCase__      =			node
							while n or stack:
														while n:
																					stack.append(A )
																					lowerCAmelCase__      =			n.left
														lowerCAmelCase__      =			stack.pop()
														print(n.data				,					end=''',''' )
														lowerCAmelCase__      =			n.right


def       _snake_case     (  A )		->					None:
							if not isinstance(A				,					A ) or not node:
														return
							lowerCAmelCase__     ,      lowerCAmelCase__      =			[], []
							lowerCAmelCase__      =			node
							stacka.append(A )
							while stacka:  # to find the reversed order of post order, store it in stack2
														lowerCAmelCase__      =			stacka.pop()
														if n.left:
																					stacka.append(n.left )
														if n.right:
																					stacka.append(n.right )
														stacka.append(A )
							while stacka:  # pop up from stack2 will be the post order
														print(stacka.pop().data				,					end=''',''' )


def       _snake_case     (  A = ""				,					A=50				,					A="*" )		->					str:
							if not s:
														return "\n" + width * char
							lowerCAmelCase__     ,      lowerCAmelCase__      =			divmod(width - len(A ) - 2				,					2 )
							return F"""{left * char} {s} {(left + extra) * char}"""


if __name__ == "__main__":
							import doctest

							doctest.testmod()
							print(prompt('''Binary Tree Traversals'''))

							__UpperCAmelCase					       =							build_tree()
							print(prompt('''Pre Order Traversal'''))
							pre_order(node)
							print(prompt() + '''\n''')

							print(prompt('''In Order Traversal'''))
							in_order(node)
							print(prompt() + '''\n''')

							print(prompt('''Post Order Traversal'''))
							post_order(node)
							print(prompt() + '''\n''')

							print(prompt('''Level Order Traversal'''))
							level_order(node)
							print(prompt() + '''\n''')

							print(prompt('''Actual Level Order Traversal'''))
							level_order_actual(node)
							print('''*''' * 50 + '''\n''')

							print(prompt('''Pre Order Traversal - Iteration Version'''))
							pre_order_iter(node)
							print(prompt() + '''\n''')

							print(prompt('''In Order Traversal - Iteration Version'''))
							in_order_iter(node)
							print(prompt() + '''\n''')

							print(prompt('''Post Order Traversal - Iteration Version'''))
							post_order_iter(node)
							print(prompt())



'''simple docstring'''






from math import pi, sqrt, tan


def       _snake_case     (  A )		->					float:
							if side_length < 0:
														raise ValueError('''surface_area_cube() only accepts non-negative values''' )
							return 6 * side_length**2


def       _snake_case     (  A				,					A				,					A )		->					float:
							if length < 0 or breadth < 0 or height < 0:
														raise ValueError('''surface_area_cuboid() only accepts non-negative values''' )
							return 2 * ((length * breadth) + (breadth * height) + (length * height))


def       _snake_case     (  A )		->					float:
							if radius < 0:
														raise ValueError('''surface_area_sphere() only accepts non-negative values''' )
							return 4 * pi * radius**2


def       _snake_case     (  A )		->					float:
							if radius < 0:
														raise ValueError('''surface_area_hemisphere() only accepts non-negative values''' )
							return 3 * pi * radius**2


def       _snake_case     (  A				,					A )		->					float:
							if radius < 0 or height < 0:
														raise ValueError('''surface_area_cone() only accepts non-negative values''' )
							return pi * radius * (radius + (height**2 + radius**2) ** 0.5)


def       _snake_case     (  A				,					A				,					A )		->					float:
							if radius_a < 0 or radius_a < 0 or height < 0:
														raise ValueError(
														    '''surface_area_conical_frustum() only accepts non-negative values''' )
							lowerCAmelCase__      =			(height**2 + (radius_a - radius_a) ** 2) ** 0.5
							return pi * ((slant_height * (radius_a + radius_a)) + radius_a**2 + radius_a**2)


def       _snake_case     (  A				,					A )		->					float:
							if radius < 0 or height < 0:
														raise ValueError('''surface_area_cylinder() only accepts non-negative values''' )
							return 2 * pi * radius * (height + radius)


def       _snake_case     (  A				,					A )		->					float:
							if torus_radius < 0 or tube_radius < 0:
														raise ValueError('''surface_area_torus() only accepts non-negative values''' )
							if torus_radius < tube_radius:
														raise ValueError(
														    '''surface_area_torus() does not support spindle or self intersecting tori''' )
							return 4 * pow(A				,					2 ) * torus_radius * tube_radius


def       _snake_case     (  A				,					A )		->					float:
							if length < 0 or width < 0:
														raise ValueError('''area_rectangle() only accepts non-negative values''' )
							return length * width


def       _snake_case     (  A )		->					float:
							if side_length < 0:
														raise ValueError('''area_square() only accepts non-negative values''' )
							return side_length**2


def       _snake_case     (  A				,					A )		->					float:
							if base < 0 or height < 0:
														raise ValueError('''area_triangle() only accepts non-negative values''' )
							return (base * height) / 2


def       _snake_case     (  A				,					A				,					A )		->					float:
							if sidea < 0 or sidea < 0 or sidea < 0:
														raise ValueError('''area_triangle_three_sides() only accepts non-negative values''' )
							elif sidea + sidea < sidea or sidea + sidea < sidea or sidea + sidea < sidea:
														raise ValueError('''Given three sides do not form a triangle''' )
							lowerCAmelCase__      =			(sidea + sidea + sidea) / 2
							lowerCAmelCase__      =			sqrt(
							    semi_perimeter
							    * (semi_perimeter - sidea)
							    * (semi_perimeter - sidea)
							    * (semi_perimeter - sidea) )
							return area


def       _snake_case     (  A				,					A )		->					float:
							if base < 0 or height < 0:
														raise ValueError('''area_parallelogram() only accepts non-negative values''' )
							return base * height


def       _snake_case     (  A				,					A				,					A )		->					float:
							if basea < 0 or basea < 0 or height < 0:
														raise ValueError('''area_trapezium() only accepts non-negative values''' )
							return 1 / 2 * (basea + basea) * height


def       _snake_case     (  A )		->					float:
							if radius < 0:
														raise ValueError('''area_circle() only accepts non-negative values''' )
							return pi * radius**2


def       _snake_case     (  A				,					A )		->					float:
							if radius_x < 0 or radius_y < 0:
														raise ValueError('''area_ellipse() only accepts non-negative values''' )
							return pi * radius_x * radius_y


def       _snake_case     (  A				,					A )		->					float:
							if diagonal_a < 0 or diagonal_a < 0:
														raise ValueError('''area_rhombus() only accepts non-negative values''' )
							return 1 / 2 * diagonal_a * diagonal_a


def       _snake_case     (  A				,					A )		->					float:
							if not isinstance(A				,					A ) or sides < 3:
														raise ValueError(
														    '''area_reg_polygon() only accepts integers greater than or \
equal to three as number of sides''' )
							elif length < 0:
														raise ValueError(
														    '''area_reg_polygon() only accepts non-negative values as \
length of a side''' )
							return (sides * length**2) / (4 * tan(pi / sides ))
							return (sides * length**2) / (4 * tan(pi / sides ))


if __name__ == "__main__":
		import doctest

		doctest.testmod(verbose=True)  # verbose so we can see methods missing tests

		print('''[DEMO] Areas of various geometric shapes: \n''')
		print(f"""Rectangle: {area_rectangle(10, 20) = }""")
		print(f"""Square: {area_square(10) = }""")
		print(f"""Triangle: {area_triangle(10, 10) = }""")
		print(f"""Triangle: {area_triangle_three_sides(5, 12, 13) = }""")
		print(f"""Parallelogram: {area_parallelogram(10, 20) = }""")
		print(f"""Rhombus: {area_rhombus(10, 20) = }""")
		print(f"""Trapezium: {area_trapezium(10, 20, 30) = }""")
		print(f"""Circle: {area_circle(20) = }""")
		print(f"""Ellipse: {area_ellipse(10, 20) = }""")
		print('''\nSurface Areas of various geometric shapes: \n''')
		print(f"""Cube: {surface_area_cube(20) = }""")
		print(f"""Cuboid: {surface_area_cuboid(10, 20, 30) = }""")
		print(f"""Sphere: {surface_area_sphere(20) = }""")
		print(f"""Hemisphere: {surface_area_hemisphere(20) = }""")
		print(f"""Cone: {surface_area_cone(10, 20) = }""")
		print(f"""Conical Frustum: {surface_area_conical_frustum(10, 20, 30) = }""")
		print(f"""Cylinder: {surface_area_cylinder(10, 20) = }""")
		print(f"""Torus: {surface_area_torus(20, 10) = }""")
		print(f"""Equilateral Triangle: {area_reg_polygon(3, 10) = }""")
		print(f"""Square: {area_reg_polygon(4, 10) = }""")
		print(f"""Reqular Pentagon: {area_reg_polygon(5, 10) = }""")