'''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 		__A       :
       snake_case       :int
       snake_case       :Node | None				    =					None
       snake_case       :Node | None				    =					None





def _lowercase	(      )					->       Node | None:





       """simple docstring"""


       __UpperCAmelCase  :				Optional[Any]       				=		Node(1						)
       __UpperCAmelCase  :				Union[str, Any]       				=		Node(2						)
       __UpperCAmelCase  :				Optional[int]       				=		Node(3						)
       __UpperCAmelCase  :				Optional[int]       				=		Node(4						)
       __UpperCAmelCase  :				List[Any]       				=		Node(5						)
       return tree

def _lowercase	(      lowerCamelCase__						)					->       list[int]:





       """simple docstring"""


       return [root.data, *preorder(root.left						), *preorder(root.right						)] if root else []

def _lowercase	(      lowerCamelCase__						)					->       list[int]:





       """simple docstring"""


       return postorder(root.left						) + postorder(root.right						) + [root.data] if root else []

def _lowercase	(      lowerCamelCase__						)					->       list[int]:





       """simple docstring"""


       return [*inorder(root.left						), root.data, *inorder(root.right						)] if root else []

def _lowercase	(      lowerCamelCase__						)					->       int:





       """simple docstring"""


       return (max(height(root.left						)							,    height(root.right						)						) + 1) if root else 0

def _lowercase	(      lowerCamelCase__						)					->       Sequence[Node | None]:





       """simple docstring"""


       __UpperCAmelCase  :				list[Any]       				=		[]

       if root is None:
              return output

       __UpperCAmelCase  :				int       				=		deque([root]						)

       while process_queue:
              __UpperCAmelCase  :				int       				=		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 _lowercase	(      lowerCamelCase__							,    lowerCamelCase__						)					->       Sequence[Node | None]:





       """simple docstring"""


       __UpperCAmelCase  :				list[Any]       				=		[]

       def populate_output(lowerCamelCase__							,    lowerCamelCase__						) -> 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 _lowercase	(      lowerCamelCase__							,    lowerCamelCase__						)					->       Sequence[Node | None]:





       """simple docstring"""


       __UpperCAmelCase  :				list[Any]       				=		[]

       def populate_output(lowerCamelCase__							,    lowerCamelCase__						) -> 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 _lowercase	(      lowerCamelCase__						)					->       Sequence[Node | None] | list[Any]:





       """simple docstring"""


       if root is None:
              return []

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

       __UpperCAmelCase  :				str       				=		0
       __UpperCAmelCase  :				Tuple       				=		height(lowerCamelCase__						)

       for h in range(1							,    height_tree + 1						):
              if not flag:
                     output.append(get_nodes_from_left_to_right(lowerCamelCase__							,    lowerCamelCase__						)						)
                     __UpperCAmelCase  :				Union[str, Any]       				=		1
              else:
                     output.append(get_nodes_from_right_to_left(lowerCamelCase__							,    lowerCamelCase__						)						)
                     __UpperCAmelCase  :				Optional[int]       				=		0

       return output

def _lowercase	(      )					->       None:  # Main function for testing.





       """simple docstring"""


       __UpperCAmelCase  :				int       				=		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()







'''simple docstring'''




def _lowercase	(      lowerCamelCase__							,    lowerCamelCase__						)					->       int:





       """simple docstring"""


       return number | (1 << position)

def _lowercase	(      lowerCamelCase__							,    lowerCamelCase__						)					->       int:





       """simple docstring"""


       return number & ~(1 << position)

def _lowercase	(      lowerCamelCase__							,    lowerCamelCase__						)					->       int:





       """simple docstring"""


       return number ^ (1 << position)

def _lowercase	(      lowerCamelCase__							,    lowerCamelCase__						)					->       bool:





       """simple docstring"""


       return ((number >> position) & 1) == 1

def _lowercase	(      lowerCamelCase__							,    lowerCamelCase__						)					->       int:





       """simple docstring"""


       return int((number & (1 << position)) != 0						)


if __name__ == "__main__":
   import doctest

   doctest.testmod()






