from __future__ import annotations

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




@dataclass
class 	__snake_case	:





      '''simple docstring'''






      _snake_case    		=       42
      _snake_case    		=       None
      _snake_case    		=       None







def 						A__  (					):







    '''simple docstring'''
    _lowerCamelCase     :		int 						=						Node(1	)
    _lowerCamelCase     :		str 						=						Node(2	)
    _lowerCamelCase     :		Dict 						=						Node(3	)
    _lowerCamelCase     :		str 						=						Node(4	)
    _lowerCamelCase     :		Any 						=						Node(5	)
    return tree







def 						A__  (					__A	):







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







def 						A__  (					__A	):







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







def 						A__  (					__A	):







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







def 						A__  (					__A	):







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







def 						A__  (					__A	):







    '''simple docstring'''
    _lowerCamelCase     :		list[Any] 						=						[]

    if root is None:
        return output

    _lowerCamelCase     :		List[str] 						=						deque([root]	)

    while process_queue:
        _lowerCamelCase     :		Tuple 						=						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 						A__  (					__A   , __A	):







    '''simple docstring'''
    _lowerCamelCase     :		list[Any] 						=						[]

    def populate_output(__A   , __A	) -> 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(__A   , __A	)
    return output







def 						A__  (					__A   , __A	):







    '''simple docstring'''
    _lowerCamelCase     :		list[Any] 						=						[]

    def populate_output(__A   , __A	) -> 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(__A   , __A	)
    return output







def 						A__  (					__A	):







    '''simple docstring'''
    if root is None:
        return []

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

    _lowerCamelCase     :		str 						=						0
    _lowerCamelCase     :		Optional[Any] 						=						height(__A	)

    for h in range(1   , height_tree + 1	):
        if not flag:
            output.append(get_nodes_from_left_to_right(__A   , __A	)	)
            _lowerCamelCase     :		List[Any] 						=						1
        else:
            output.append(get_nodes_from_right_to_left(__A   , __A	)	)
            _lowerCamelCase     :		List[Any] 						=						0

    return output







def 						A__  (					):  # Main function for testing.







    '''simple docstring'''
    _lowerCamelCase     :		Dict 						=						make_tree()
    print(F"""In-order Traversal: {inorder(__A	)}"""	)
    print(F"""Pre-order Traversal: {preorder(__A	)}"""	)
    print(F"""Post-order Traversal: {postorder(__A	)}"""   , """\n"""	)

    print(F"""Height of Tree: {height(__A	)}"""   , """\n"""	)

    print("""Complete Level Order Traversal: """	)
    print(level_order(__A	)   , """\n"""	)

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

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

    print("""\nZigZag order Traversal: """	)
    print(zigzag(__A	)	)


if __name__ == "__main__":
    import doctest

    doctest.testmod()
    main()





import math







def 						A__  (					__A	):







    '''simple docstring'''
    assert isinstance(__A   , __A	) and (
        number >= 0
    ), "'number' must been an int and positive"

    if 1 < number < 4:
        # 2 and 3 are primes
        return True
    elif number < 2 or not number % 2:
        # Negatives, 0, 1 and all even numbers are not primes
        return False

    _lowerCamelCase     :		List[Any] 						=						range(3   , int(math.sqrt(__A	) + 1	)   , 2	)
    return not any(not number % i for i in odd_numbers	)







def 						A__  (					__A   , __A=1   , **__A	):







    '''simple docstring'''
    _lowerCamelCase     :		Dict 						=						factor * value
    _lowerCamelCase     :		str 						=						value

    while not is_prime(__A	):
        value += 1 if not ("desc" in kwargs and kwargs["desc"] is True) else -1

    if value == first_value_val:
        return next_prime(value + 1   , **__A	)
    return value




