from __future__ import annotations

from collections import deque
from collections.abc import Sequence
from dataclasses import dataclass
from typing import Any
@dataclass
class     lowerCAmelCase_     :
							UpperCAmelCase				   =     42
							UpperCAmelCase				   =     None
							UpperCAmelCase				   =     None




def 					_snake_case	(  ):
					_UpperCamelCase			     =     Node(1						)
					_UpperCamelCase			     =     Node(2						)
					_UpperCamelCase			     =     Node(3						)
					_UpperCamelCase			     =     Node(4						)
					_UpperCamelCase			     =     Node(5						)
					return tree
def 					_snake_case	(  __snake_case						):
					return [root.data, *preorder(root.left						), *preorder(root.right						)] if root else []
def 					_snake_case	(  __snake_case						):
					return postorder(root.left						) + postorder(root.right						) + [root.data] if root else []
def 					_snake_case	(  __snake_case						):
					return [*inorder(root.left						), root.data, *inorder(root.right						)] if root else []
def 					_snake_case	(  __snake_case						):
					return (max(height(root.left						)  ,     height(root.right						)						) + 1) if root else 0
def 					_snake_case	(  __snake_case						):
					_UpperCamelCase			     =     []

					if root is None:
										return output

					_UpperCamelCase			     =     deque([root]						)

					while process_queue:
										_UpperCamelCase			     =     process_queue.popleft()
										output.append(node.data						)

										if node.left:
															process_queue.append(node.left						)
										if node.right:
															process_queue.append(node.right						)
					return output
def 					_snake_case	(  __snake_case  ,     __snake_case						):
					_UpperCamelCase			     =     []

					def populate_output(__snake_case  ,     __snake_case						) -> None:
										if not root:
															return
										if level == 1:
															output.append(root.data						)
										elif level > 1:
															populate_output(root.left  ,     level - 1						)
															populate_output(root.right  ,     level - 1						)

					populate_output(__snake_case  ,     __snake_case						)
					return output
def 					_snake_case	(  __snake_case  ,     __snake_case						):
					_UpperCamelCase			     =     []

					def populate_output(__snake_case  ,     __snake_case						) -> None:
										if root is None:
															return
										if level == 1:
															output.append(root.data						)
										elif level > 1:
															populate_output(root.right  ,     level - 1						)
															populate_output(root.left  ,     level - 1						)

					populate_output(__snake_case  ,     __snake_case						)
					return output
def 					_snake_case	(  __snake_case						):
					if root is None:
										return []

					_UpperCamelCase			     =     []

					_UpperCamelCase			     =     0
					_UpperCamelCase			     =     height(__snake_case						)

					for h in range(1  ,     height_tree + 1						):
										if not flag:
															output.append(get_nodes_from_left_to_right(__snake_case  ,     __snake_case						)						)
															_UpperCamelCase			     =     1
										else:
															output.append(get_nodes_from_right_to_left(__snake_case  ,     __snake_case						)						)
															_UpperCamelCase			     =     0

					return output
def 					_snake_case	(  ):  # Main function for testing.
					_UpperCamelCase			     =     make_tree()
					print(f"""In-order Traversal: {inorder(__snake_case						)}"""						)
					print(f"""Pre-order Traversal: {preorder(__snake_case						)}"""						)
					print(f"""Post-order Traversal: {postorder(__snake_case						)}"""  ,     '''\n'''						)

					print(f"""Height of Tree: {height(__snake_case						)}"""  ,     '''\n'''						)

					print('''Complete Level Order Traversal: '''						)
					print(level_order(__snake_case						)  ,     '''\n'''						)

					print('''Level-wise order Traversal: '''						)

					for level in range(1  ,     height(__snake_case						) + 1						):
										print(f"""Level {level}:"""  ,     get_nodes_from_left_to_right(__snake_case  ,     level=__snake_case						)						)

					print('''\nZigZag order Traversal: '''						)
					print(zigzag(__snake_case						)						)


if __name__ == "__main__":
					import doctest

					doctest.testmod()
					main()






"""simple docstring"""






from __future__ import annotations







def 	_snake_case     (							lowercase__						):
				_lowerCamelCase	:     int       =       len(lowercase__						)
				# We need to create solution object to save path.
				_lowerCamelCase	:     Tuple       =       [[0 for _ in range(lowercase__						)] for _ in range(lowercase__						)]
				_lowerCamelCase	:     Optional[Any]       =       run_maze(lowercase__				,       0				,       0				,       lowercase__						)
				if solved:
								print('\n'.join(str(lowercase__						) for row in solutions						)						)
				else:
								print('No solution exists!'						)
				return solved







def 	_snake_case     (							lowercase__				,       lowercase__				,       lowercase__				,       lowercase__						):
				_lowerCamelCase	:     Optional[int]       =       len(lowercase__						)
				# Final check point.
				if i == j == (size - 1):
								_lowerCamelCase	:     Optional[Any]       =       1
								return True

				_lowerCamelCase	:     List[str]       =       (not i < 0) and (not j < 0)  # Check lower bounds
				_lowerCamelCase	:     List[str]       =       (i < size) and (j < size)  # Check upper bounds

				if lower_flag and upper_flag:
								# check for already visited and block points.
								_lowerCamelCase	:     List[Any]       =       (not solutions[i][j]) and (not maze[i][j])
								if block_flag:
												# check visited
												_lowerCamelCase	:     Union[str, Any]       =       1

												# check for directions
												if (
												    run_maze(lowercase__				,       i + 1				,       lowercase__				,       lowercase__						)
												    or run_maze(lowercase__				,       lowercase__				,       j + 1				,       lowercase__						)
												    or run_maze(lowercase__				,       i - 1				,       lowercase__				,       lowercase__						)
												    or run_maze(lowercase__				,       lowercase__				,       j - 1				,       lowercase__						)
												):
																return True

												_lowerCamelCase	:     Dict       =       0
												return False
				return False


if __name__ == "__main__":
			import doctest

			doctest.testmod()