





from __future__ import annotations

class 		UpperCamelCase__			:



     '''simple docstring'''

     def __init__(							self						:   List[str]						,lowerCamelCase__						:   int	)					->		None:




           '''simple docstring'''


           SCREAMING_SNAKE_CASE		=						data
           SCREAMING_SNAKE_CASE		=						None
           SCREAMING_SNAKE_CASE		=						None



def        __lowercase       (				_SCREAMING_SNAKE_CASE     )			->       None:  # In Order traversal of the tree


      '''simple docstring'''


      if tree:
            display(tree.left     )
            print(tree.data     )
            display(tree.right     )



def        __lowercase       (				_SCREAMING_SNAKE_CASE     )			->       int:


      '''simple docstring'''


      return 1 + max(depth_of_tree(tree.left     )			,						depth_of_tree(tree.right     )     ) if tree else 0



def        __lowercase       (				_SCREAMING_SNAKE_CASE     )			->       bool:


      '''simple docstring'''


      if not tree:
            return True
      if tree.left and tree.right:
            return is_full_binary_tree(tree.left     ) and is_full_binary_tree(tree.right     )
      else:
            return not tree.left and not tree.right



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


      '''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     )
      SCREAMING_SNAKE_CASE		=						Node(6     )
      SCREAMING_SNAKE_CASE		=						Node(7     )
      SCREAMING_SNAKE_CASE		=						Node(8     )
      SCREAMING_SNAKE_CASE		=						Node(9     )

      print(is_full_binary_tree(_SCREAMING_SNAKE_CASE     )     )
      print(depth_of_tree(_SCREAMING_SNAKE_CASE     )     )
      print("""Tree is: """     )
      display(_SCREAMING_SNAKE_CASE     )


if __name__ == "__main__":
      main()









def        __lowercase       (				_SCREAMING_SNAKE_CASE = 50     )			->       int:


      '''simple docstring'''


      SCREAMING_SNAKE_CASE		=						[1] * (length + 1)

      for row_length in range(3			,						length + 1     ):
            for block_length in range(3			,						row_length + 1     ):
                  for block_start in range(row_length - block_length     ):
                        ways_number[row_length] += ways_number[
                            row_length - block_start - block_length - 1
                        ]

                  ways_number[row_length] += 1

      return ways_number[length]


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


