

'''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__   :
  A__					=    42
  A__					=    None
  A__					=    None


def 	_lowerCAmelCase (						)				->      Node | None:
     """simple docstring"""




     _SCREAMING_SNAKE_CASE							   =Node(1    )
     _SCREAMING_SNAKE_CASE							   =Node(2    )
     _SCREAMING_SNAKE_CASE							   =Node(3    )
     _SCREAMING_SNAKE_CASE							   =Node(4    )
     _SCREAMING_SNAKE_CASE							   =Node(5    )
     return tree


def 	_lowerCAmelCase (						_UpperCamelCase						:					Node | None    )				->      list[int]:
     """simple docstring"""




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


def 	_lowerCAmelCase (						_UpperCamelCase						:					Node | None    )				->      list[int]:
     """simple docstring"""




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


def 	_lowerCAmelCase (						_UpperCamelCase						:					Node | None    )				->      list[int]:
     """simple docstring"""




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


def 	_lowerCAmelCase (						_UpperCamelCase						:					Node | None    )				->      int:
     """simple docstring"""




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


def 	_lowerCAmelCase (						_UpperCamelCase						:					Node | None    )				->      Sequence[Node | None]:
     """simple docstring"""




     _SCREAMING_SNAKE_CASE							   =[]

     if root is None:
          return output

     _SCREAMING_SNAKE_CASE							   =deque([root]    )

     while process_queue:
          _SCREAMING_SNAKE_CASE							   =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 	_lowerCAmelCase (						_UpperCamelCase						:					Node | None							,			_UpperCamelCase						:					int    )				->      Sequence[Node | None]:
     """simple docstring"""




     _SCREAMING_SNAKE_CASE							   =[]

     def populate_output(_UpperCamelCase						:					Node | None							,			_UpperCamelCase						:					int    ) -> 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(_UpperCamelCase							,			_UpperCamelCase    )
     return output


def 	_lowerCAmelCase (						_UpperCamelCase						:					Node | None							,			_UpperCamelCase						:					int    )				->      Sequence[Node | None]:
     """simple docstring"""




     _SCREAMING_SNAKE_CASE							   =[]

     def populate_output(_UpperCamelCase						:					Node | None							,			_UpperCamelCase						:					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(_UpperCamelCase							,			_UpperCamelCase    )
     return output


def 	_lowerCAmelCase (						_UpperCamelCase						:					Node | None    )				->      Sequence[Node | None] | list[Any]:
     """simple docstring"""




     if root is None:
          return []

     _SCREAMING_SNAKE_CASE							   =[]

     _SCREAMING_SNAKE_CASE							   =0
     _SCREAMING_SNAKE_CASE							   =height(_UpperCamelCase    )

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

     return output


def 	_lowerCAmelCase (						)				->      None:  # Main function for testing.
     """simple docstring"""




     _SCREAMING_SNAKE_CASE							   =make_tree()
     print(f"In-order Traversal: {inorder(_UpperCamelCase    )}"    )
     print(f"Pre-order Traversal: {preorder(_UpperCamelCase    )}"    )
     print(f"Post-order Traversal: {postorder(_UpperCamelCase    )}"							,			'\n'    )

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

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

     print('Level-wise order Traversal: '    )

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

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


if __name__ == "__main__":
     import doctest

     doctest.testmod()
     main()



'''simple docstring'''
def 	_lowerCAmelCase (						_UpperCamelCase						:					int = 50    )				->      int:
     """simple docstring"""




     _SCREAMING_SNAKE_CASE							   =[[0] * 3 for _ in range(length + 1    )]

     for row_length in range(length + 1    ):
          for tile_length in range(2							,			5    ):
               for tile_start in range(row_length - tile_length + 1    ):
                    different_colour_ways_number[row_length][tile_length - 2] += (
                        different_colour_ways_number[row_length - tile_start - tile_length][
                            tile_length - 2
                        ]
                        + 1
                    )

     return sum(different_colour_ways_number[length]    )


if __name__ == "__main__":
     print(f'''{solution() = }''')
