





from __future__ import annotations



class 				_UpperCAmelCase    :

  """simple docstring"""


  def __init__(				self :		Union[str, Any]					,  lowerCAmelCase_ :		Optional[Any]     )							->						Any:
     __lowerCAmelCase								=	data
     __lowerCAmelCase								=	None
     __lowerCAmelCase								=	None





def   a_    ( lowerCAmelCase_      :			Node | None	):  # In Order traversal of the tree
   if tree:
      display(tree.left	)
      print(tree.data	)
      display(tree.right	)

def   a_    ( lowerCAmelCase_      :			Node | None	):
   return 1 + max(depth_of_tree(tree.left	),	depth_of_tree(tree.right	)	) if tree else 0

def   a_    ( lowerCAmelCase_      :			Node	):
   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   a_    ( ):  # Main function for testing.
   __lowerCAmelCase								=	Node(1	)
   __lowerCAmelCase								=	Node(2	)
   __lowerCAmelCase								=	Node(3	)
   __lowerCAmelCase								=	Node(4	)
   __lowerCAmelCase								=	Node(5	)
   __lowerCAmelCase								=	Node(6	)
   __lowerCAmelCase								=	Node(7	)
   __lowerCAmelCase								=	Node(8	)
   __lowerCAmelCase								=	Node(9	)

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


if __name__ == "__main__":
     main()








def 	UpperCamelCase__(       UpperCamelCase__			:       Dict  )->Dict:
       # if the collection is empty, returns empty
       if collection == []:
              return []

       # get some information about the collection
       A__											=						len(UpperCamelCase__  )
       A__											=						max(UpperCamelCase__  )
       A__											=						min(UpperCamelCase__  )

       # create the counting array
       A__											=						coll_max + 1 - coll_min
       A__											=						[0] * counting_arr_length

       # count how much a number appears in the collection
       for number in collection:
              counting_arr[number - coll_min] += 1

       # sum each position with it's predecessors. now, counting_arr[i] tells
       # us how many elements <= i has in the collection
       for i in range(1 ,     UpperCamelCase__  ):
              A__											=						counting_arr[i] + counting_arr[i - 1]

       # create the output collection
       A__											=						[0] * coll_len

       # place the elements in the output, respecting the original order (stable
       # sort) from end to begin, updating counting_arr
       for i in reversed(range(0 ,     UpperCamelCase__  )  ):
              A__											=						collection[i]
              counting_arr[collection[i] - coll_min] -= 1

       return ordered


def 	UpperCamelCase__(       UpperCamelCase__			:       Optional[int]  )->Tuple:
       return "".join([chr(UpperCamelCase__  ) for i in counting_sort([ord(UpperCamelCase__  ) for c in string]  )]  )


if __name__ == "__main__":
       # Test string sort
       assert counting_sort_string('thisisthestring') == "eghhiiinrsssttt"

       a__:      Dict									=		input('Enter numbers separated by a comma:\n').strip()
       a__:      Any									=		[int(item) for item in user_input.split(',')]
       print(counting_sort(unsorted))





