



'''simple docstring'''






from __future__ import annotations

from collections import deque
from collections.abc import Sequence
from dataclasses import dataclass
from typing import Any

@dataclass
class 				SCREAMING_SNAKE_CASE:







	"""simple docstring"""






	lowerCamelCase__			 =       42
	lowerCamelCase__			 =       None
	lowerCamelCase__			 =       None


def  snake_case_     (					)      ->   Any:
							UpperCAmelCase :       str 							=		Node(1  )
							UpperCAmelCase :       int 							=		Node(2  )
							UpperCAmelCase :       Dict 							=		Node(3  )
							UpperCAmelCase :       int 							=		Node(4  )
							UpperCAmelCase :       List[str] 							=		Node(5  )
							return tree


def  snake_case_     (					_lowerCAmelCase  :						Tuple  )      ->   Tuple:
							return [root.data, *preorder(root.left  ), *preorder(root.right  )] if root else []


def  snake_case_     (					_lowerCAmelCase  :						Optional[int]  )      ->   Optional[int]:
							return postorder(root.left  ) + postorder(root.right  ) + [root.data] if root else []


def  snake_case_     (					_lowerCAmelCase  :						List[str]  )      ->   Dict:
							return [*inorder(root.left  ), root.data, *inorder(root.right  )] if root else []


def  snake_case_     (					_lowerCAmelCase  :						Any  )      ->   Any:
							return (max(height(root.left  )   ,      height(root.right  )  ) + 1) if root else 0


def  snake_case_     (					_lowerCAmelCase  :						Any  )      ->   Union[str, Any]:
							UpperCAmelCase :       list[Any] 							=		[]

							if root is None:
														return output

							UpperCAmelCase :       Optional[int] 							=		deque([root]  )

							while process_queue:
														UpperCAmelCase :       Dict 							=		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_     (					_lowerCAmelCase  :						str   ,      _lowerCAmelCase  :						Tuple  )      ->   Optional[Any]:
							UpperCAmelCase :       list[Any] 							=		[]

							def populate_output(_lowerCAmelCase  :						List[str]   ,      _lowerCAmelCase  :						Tuple  ) -> 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(_lowerCAmelCase   ,      _lowerCAmelCase  )
							return output


def  snake_case_     (					_lowerCAmelCase  :						List[Any]   ,      _lowerCAmelCase  :						Dict  )      ->   List[Any]:
							UpperCAmelCase :       list[Any] 							=		[]

							def populate_output(_lowerCAmelCase  :						Optional[Any]   ,      _lowerCAmelCase  :						Optional[int]  ) -> 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(_lowerCAmelCase   ,      _lowerCAmelCase  )
							return output


def  snake_case_     (					_lowerCAmelCase  :						Tuple  )      ->   Any:
							if root is None:
														return []

							UpperCAmelCase :       list[Sequence[Node | None]] 							=		[]

							UpperCAmelCase :       Optional[int] 							=		0
							UpperCAmelCase :       List[Any] 							=		height(_lowerCAmelCase  )

							for h in range(1   ,      height_tree + 1  ):
														if not flag:
																					output.append(get_nodes_from_left_to_right(_lowerCAmelCase   ,      _lowerCAmelCase  )  )
																					UpperCAmelCase :       int 							=		1
														else:
																					output.append(get_nodes_from_right_to_left(_lowerCAmelCase   ,      _lowerCAmelCase  )  )
																					UpperCAmelCase :       Any 							=		0

							return output


def  snake_case_     (					)      ->   Dict:  # Main function for testing.
							UpperCAmelCase :       List[Any] 							=		make_tree()
							print(f"""In-order Traversal: {inorder(_lowerCAmelCase  )}"""  )
							print(f"""Pre-order Traversal: {preorder(_lowerCAmelCase  )}"""  )
							print(f"""Post-order Traversal: {postorder(_lowerCAmelCase  )}"""   ,      '''\n'''  )

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

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

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

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

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


if __name__ == "__main__":
						import doctest

						doctest.testmod()
						main()







def     _a					(						lowerCamelCase							):

 if p < 2:
  raise ValueError("""p should not be less than 2!"""							)
 elif p == 2:
  return True

 lowerCamelCase		:	Any							=      4
 lowerCamelCase		:	List[str]							=      (1 << p) - 1
 for _ in range(p - 2							):
  lowerCamelCase		:	List[Any]							=      ((s * s) - 2) % m
 return s == 0


if __name__ == "__main__":
      print(lucas_lehmer_test(7))
      print(lucas_lehmer_test(1_1))




