





'''simple docstring'''






import os
import string
import sys


snake_case_     =	1 << 8

snake_case_     =	{
    """tab""": ord("""\t"""),
    """newline""": ord("""\r"""),
    """esc""": 27,
    """up""": 65 + ARROW_KEY_FLAG,
    """down""": 66 + ARROW_KEY_FLAG,
    """right""": 67 + ARROW_KEY_FLAG,
    """left""": 68 + ARROW_KEY_FLAG,
    """mod_int""": 91,
    """undefined""": sys.maxsize,
    """interrupt""": 3,
    """insert""": 50,
    """delete""": 51,
    """pg_up""": 53,
    """pg_down""": 54,
}

snake_case_     =	KEYMAP["""up"""]
snake_case_     =	KEYMAP["""left"""]

if sys.platform == "win32":
     snake_case_     =	[]
     snake_case_     =	{
         b"""\xe0H""": KEYMAP["""up"""] - ARROW_KEY_FLAG,
         b"""\x00H""": KEYMAP["""up"""] - ARROW_KEY_FLAG,
         b"""\xe0P""": KEYMAP["""down"""] - ARROW_KEY_FLAG,
         b"""\x00P""": KEYMAP["""down"""] - ARROW_KEY_FLAG,
         b"""\xe0M""": KEYMAP["""right"""] - ARROW_KEY_FLAG,
         b"""\x00M""": KEYMAP["""right"""] - ARROW_KEY_FLAG,
         b"""\xe0K""": KEYMAP["""left"""] - ARROW_KEY_FLAG,
         b"""\x00K""": KEYMAP["""left"""] - ARROW_KEY_FLAG,
     }

for i in range(10):
     snake_case_     =	ord(str(i))
def 							_lowerCamelCase(  )		->  Optional[Any]:
    if os.name == "nt":
        import msvcrt

        A       :       Any							=						'''mbcs'''
        # Flush the keyboard buffer
        while msvcrt.kbhit():
            msvcrt.getch()
        if len(UpperCamelCase__		) == 0:
            # Read the keystroke
            A       :       Tuple							=						msvcrt.getch()

            # If it is a prefix char, get second part
            if ch in (b"\x00", b"\xe0"):
                A       :       int							=						ch + msvcrt.getch()
                # Translate actual Win chars to bullet char types
                try:
                    A       :       List[Any]							=						chr(WIN_KEYMAP[cha]		)
                    WIN_CH_BUFFER.append(chr(KEYMAP['''mod_int''']		)		)
                    WIN_CH_BUFFER.append(UpperCamelCase__		)
                    if ord(UpperCamelCase__		) in (
                        KEYMAP["insert"] - 1 << 9,
                        KEYMAP["delete"] - 1 << 9,
                        KEYMAP["pg_up"] - 1 << 9,
                        KEYMAP["pg_down"] - 1 << 9,
                    ):
                        WIN_CH_BUFFER.append(chr(126		)		)
                    A       :       int							=						chr(KEYMAP['''esc''']		)
                except KeyError:
                    A       :       List[str]							=						cha[1]
            else:
                A       :       Any							=						ch.decode(UpperCamelCase__		)
        else:
            A       :       List[str]							=						WIN_CH_BUFFER.pop(0		)
    elif os.name == "posix":
        import termios
        import tty

        A       :       List[Any]							=						sys.stdin.fileno()
        A       :       int							=						termios.tcgetattr(UpperCamelCase__		)
        try:
            tty.setraw(UpperCamelCase__		)
            A       :       Optional[int]							=						sys.stdin.read(1		)
        finally:
            termios.tcsetattr(UpperCamelCase__    ,       termios.TCSADRAIN    ,       UpperCamelCase__		)
    return ch





def 							_lowerCamelCase(  )		->  Optional[Any]:
    A       :       str							=						get_raw_chars()
    if ord(UpperCamelCase__		) in [KEYMAP["interrupt"], KEYMAP["newline"]]:
        return char

    elif ord(UpperCamelCase__		) == KEYMAP["esc"]:
        A       :       List[str]							=						get_raw_chars()
        if ord(UpperCamelCase__		) == KEYMAP["mod_int"]:
            A       :       Optional[Any]							=						get_raw_chars()
            if ord(UpperCamelCase__		) >= KEYMAP["arrow_begin"] - ARROW_KEY_FLAG and ord(UpperCamelCase__		) <= KEYMAP["arrow_end"] - ARROW_KEY_FLAG:
                return chr(ord(UpperCamelCase__		) + ARROW_KEY_FLAG		)
            else:
                return KEYMAP["undefined"]
        else:
            return get_raw_chars()

    else:
        if char in string.printable:
            return char
        else:
            return KEYMAP["undefined"]







'''simple docstring'''






from __future__ import annotations


class   _lowercase						:


   def __init__( self    ,   _UpperCAmelCase					):
       A       :       str							=						data
       A       :       Node | None							=						None
       A       :       Node | None							=						None







def 							_lowerCamelCase(  UpperCamelCase__    : Node | None		)		->  None:  # In Order traversal of the tree
    if tree:
        display(tree.left		)
        print(tree.data		)
        display(tree.right		)
def 							_lowerCamelCase(  UpperCamelCase__    : Node | None		)		->  int:
    return 1 + max(depth_of_tree(tree.left		)    ,       depth_of_tree(tree.right		)		) if tree else 0
def 							_lowerCamelCase(  UpperCamelCase__    : Node		)		->  bool:
    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 							_lowerCamelCase(  )		->  None:  # Main function for testing.
    A       :       Optional[int]							=						Node(1		)
    A       :       Tuple							=						Node(2		)
    A       :       Dict							=						Node(3		)
    A       :       List[str]							=						Node(4		)
    A       :       Union[str, Any]							=						Node(5		)
    A       :       str							=						Node(6		)
    A       :       Any							=						Node(7		)
    A       :       str							=						Node(8		)
    A       :       Optional[int]							=						Node(9		)

    print(is_full_binary_tree(UpperCamelCase__		)		)
    print(depth_of_tree(UpperCamelCase__		)		)
    print('''Tree is: '''		)
    display(UpperCamelCase__		)


if __name__ == "__main__":
     main()
