



from __future__ import annotations

import unittest
from collections.abc import Iterator





class 		UpperCAmelCase    :





   def __init__(						self							,  _lowerCAmelCase							,  _lowerCAmelCase      ):
         _lowerCAmelCase			      =	label
         _lowerCAmelCase			      =	parent
         _lowerCAmelCase			      =	None
         _lowerCAmelCase			      =	None






class 		UpperCAmelCase    :





   def __init__(						self      ):
         _lowerCAmelCase			      =	None





   def 						__lowerCAmelCase				(						self      ):
         _lowerCAmelCase			      =	None





   def 						__lowerCAmelCase				(						self      ):
         return self.root is None





   def 						__lowerCAmelCase				(						self							,  _lowerCAmelCase      ):
         _lowerCAmelCase			      =	self._put(self.root							,  _lowerCAmelCase      )





   def 						__lowerCAmelCase				(						self							,  _lowerCAmelCase							,  _lowerCAmelCase							,  _lowerCAmelCase = None      ):
         if node is None:
               _lowerCAmelCase			      =	Node(_lowerCAmelCase							,  _lowerCAmelCase      )
         else:
               if label < node.label:
                     _lowerCAmelCase			      =	self._put(node.left							,  _lowerCAmelCase							,  _lowerCAmelCase      )
               elif label > node.label:
                     _lowerCAmelCase			      =	self._put(node.right							,  _lowerCAmelCase							,  _lowerCAmelCase      )
               else:
                     _lowerCAmelCase			      =	F'''Node with label {label} already exists'''
                     raise Exception(_lowerCAmelCase      )

         return node





   def 						__lowerCAmelCase				(						self							,  _lowerCAmelCase      ):
         return self._search(self.root							,  _lowerCAmelCase      )





   def 						__lowerCAmelCase				(						self							,  _lowerCAmelCase							,  _lowerCAmelCase      ):
         if node is None:
               _lowerCAmelCase			      =	F'''Node with label {label} does not exist'''
               raise Exception(_lowerCAmelCase      )
         else:
               if label < node.label:
                     _lowerCAmelCase			      =	self._search(node.left							,  _lowerCAmelCase      )
               elif label > node.label:
                     _lowerCAmelCase			      =	self._search(node.right							,  _lowerCAmelCase      )

         return node





   def 						__lowerCAmelCase				(						self							,  _lowerCAmelCase      ):
         _lowerCAmelCase			      =	self.search(_lowerCAmelCase      )
         if node.right and node.left:
               _lowerCAmelCase			      =	self._get_lowest_node(node.right      )
               _lowerCAmelCase			      =	node.left
               _lowerCAmelCase			      =	node.right
               _lowerCAmelCase			      =	lowest_node
               if node.right:
                     _lowerCAmelCase			      =	lowest_node
               self._reassign_nodes(_lowerCAmelCase							,  _lowerCAmelCase      )
         elif not node.right and node.left:
               self._reassign_nodes(_lowerCAmelCase							,  node.left      )
         elif node.right and not node.left:
               self._reassign_nodes(_lowerCAmelCase							,  node.right      )
         else:
               self._reassign_nodes(_lowerCAmelCase							,  _lowerCAmelCase      )





   def 						__lowerCAmelCase				(						self							,  _lowerCAmelCase							,  _lowerCAmelCase      ):
         if new_children:
               _lowerCAmelCase			      =	node.parent

         if node.parent:
               if node.parent.right == node:
                     _lowerCAmelCase			      =	new_children
               else:
                     _lowerCAmelCase			      =	new_children
         else:
               _lowerCAmelCase			      =	new_children





   def 						__lowerCAmelCase				(						self							,  _lowerCAmelCase      ):
         if node.left:
               _lowerCAmelCase			      =	self._get_lowest_node(node.left      )
         else:
               _lowerCAmelCase			      =	node
               self._reassign_nodes(_lowerCAmelCase							,  node.right      )

         return lowest_node





   def 						__lowerCAmelCase				(						self							,  _lowerCAmelCase      ):
         try:
               self.search(_lowerCAmelCase      )
               return True
         except Exception:
               return False





   def 						__lowerCAmelCase				(						self      ):
         if self.root is None:
               raise Exception('''Binary search tree is empty'''      )

         _lowerCAmelCase			      =	self.root
         while node.right is not None:
               _lowerCAmelCase			      =	node.right

         return node.label





   def 						__lowerCAmelCase				(						self      ):
         if self.root is None:
               raise Exception('''Binary search tree is empty'''      )

         _lowerCAmelCase			      =	self.root
         while node.left is not None:
               _lowerCAmelCase			      =	node.left

         return node.label





   def 						__lowerCAmelCase				(						self      ):
         return self._inorder_traversal(self.root      )





   def 						__lowerCAmelCase				(						self							,  _lowerCAmelCase      ):
         if node is not None:
               yield from self._inorder_traversal(node.left      )
               yield node
               yield from self._inorder_traversal(node.right      )





   def 						__lowerCAmelCase				(						self      ):
         return self._preorder_traversal(self.root      )





   def 						__lowerCAmelCase				(						self							,  _lowerCAmelCase      ):
         if node is not None:
               yield node
               yield from self._preorder_traversal(node.left      )
               yield from self._preorder_traversal(node.right      )






class 		UpperCAmelCase    (    unittest.TestCase					):





   @staticmethod
   def 						__lowerCAmelCase				(						):
         _lowerCAmelCase			      =	BinarySearchTree()
         t.put(8      )
         t.put(3      )
         t.put(6      )
         t.put(1      )
         t.put(10      )
         t.put(14      )
         t.put(13      )
         t.put(4      )
         t.put(7      )
         t.put(5      )

         return t





   def 						__lowerCAmelCase				(						self      ):
         _lowerCAmelCase			      =	BinarySearchTree()
         assert t.is_empty()

         t.put(8      )
         assert t.root is not None
         assert t.root.parent is None
         assert t.root.label == 8

         t.put(10      )
         assert t.root.right is not None
         assert t.root.right.parent == t.root
         assert t.root.right.label == 10

         t.put(3      )
         assert t.root.left is not None
         assert t.root.left.parent == t.root
         assert t.root.left.label == 3

         t.put(6      )
         assert t.root.left.right is not None
         assert t.root.left.right.parent == t.root.left
         assert t.root.left.right.label == 6

         t.put(1      )
         assert t.root.left.left is not None
         assert t.root.left.left.parent == t.root.left
         assert t.root.left.left.label == 1

         with self.assertRaises(_lowerCAmelCase      ):  # noqa: B017
               t.put(1      )





   def 						__lowerCAmelCase				(						self      ):
         _lowerCAmelCase			      =	self._get_binary_search_tree()

         _lowerCAmelCase			      =	t.search(6      )
         assert node.label == 6

         _lowerCAmelCase			      =	t.search(13      )
         assert node.label == 13

         with self.assertRaises(_lowerCAmelCase      ):  # noqa: B017
               t.search(2      )





   def 						__lowerCAmelCase				(						self      ):
         _lowerCAmelCase			      =	self._get_binary_search_tree()

         t.remove(13      )
         assert t.root is not None
         assert t.root.right is not None
         assert t.root.right.right is not None
         assert t.root.right.right.right is None
         assert t.root.right.right.left is None

         t.remove(7      )
         assert t.root.left is not None
         assert t.root.left.right is not None
         assert t.root.left.right.left is not None
         assert t.root.left.right.right is None
         assert t.root.left.right.left.label == 4

         t.remove(6      )
         assert t.root.left.left is not None
         assert t.root.left.right.right is not None
         assert t.root.left.left.label == 1
         assert t.root.left.right.label == 4
         assert t.root.left.right.right.label == 5
         assert t.root.left.right.left is None
         assert t.root.left.left.parent == t.root.left
         assert t.root.left.right.parent == t.root.left

         t.remove(3      )
         assert t.root is not None
         assert t.root.left.label == 4
         assert t.root.left.right.label == 5
         assert t.root.left.left.label == 1
         assert t.root.left.parent == t.root
         assert t.root.left.left.parent == t.root.left
         assert t.root.left.right.parent == t.root.left

         t.remove(4      )
         assert t.root.left is not None
         assert t.root.left.left is not None
         assert t.root.left.label == 5
         assert t.root.left.right is None
         assert t.root.left.left.label == 1
         assert t.root.left.parent == t.root
         assert t.root.left.left.parent == t.root.left





   def 						__lowerCAmelCase				(						self      ):
         _lowerCAmelCase			      =	self._get_binary_search_tree()

         t.remove(3      )
         assert t.root is not None
         assert t.root.left is not None
         assert t.root.left.left is not None
         assert t.root.left.right is not None
         assert t.root.left.right.left is not None
         assert t.root.left.right.right is not None
         assert t.root.left.label == 4
         assert t.root.left.right.label == 6
         assert t.root.left.left.label == 1
         assert t.root.left.right.right.label == 7
         assert t.root.left.right.left.label == 5
         assert t.root.left.parent == t.root
         assert t.root.left.right.parent == t.root.left
         assert t.root.left.left.parent == t.root.left
         assert t.root.left.right.left.parent == t.root.left.right





   def 						__lowerCAmelCase				(						self      ):
         _lowerCAmelCase			      =	self._get_binary_search_tree()
         t.empty()
         assert t.root is None





   def 						__lowerCAmelCase				(						self      ):
         _lowerCAmelCase			      =	self._get_binary_search_tree()
         assert not t.is_empty()

         t.empty()
         assert t.is_empty()





   def 						__lowerCAmelCase				(						self      ):
         _lowerCAmelCase			      =	self._get_binary_search_tree()

         assert t.exists(6      )
         assert not t.exists(-1      )





   def 						__lowerCAmelCase				(						self      ):
         _lowerCAmelCase			      =	self._get_binary_search_tree()

         assert t.get_max_label() == 14

         t.empty()
         with self.assertRaises(_lowerCAmelCase      ):  # noqa: B017
               t.get_max_label()





   def 						__lowerCAmelCase				(						self      ):
         _lowerCAmelCase			      =	self._get_binary_search_tree()

         assert t.get_min_label() == 1

         t.empty()
         with self.assertRaises(_lowerCAmelCase      ):  # noqa: B017
               t.get_min_label()





   def 						__lowerCAmelCase				(						self      ):
         _lowerCAmelCase			      =	self._get_binary_search_tree()

         _lowerCAmelCase			      =	[i.label for i in t.inorder_traversal()]
         assert inorder_traversal_nodes == [1, 3, 4, 5, 6, 7, 8, 10, 13, 14]





   def 						__lowerCAmelCase				(						self      ):
         _lowerCAmelCase			      =	self._get_binary_search_tree()

         _lowerCAmelCase			      =	[i.label for i in t.preorder_traversal()]
         assert preorder_traversal_nodes == [8, 3, 1, 6, 4, 5, 7, 10, 14, 13]






def 				UpperCAmelCase__		(					)->None:
      _lowerCAmelCase			      =	BinarySearchTree()
      t.put(8					)
      t.put(3					)
      t.put(6					)
      t.put(1					)
      t.put(1_0					)
      t.put(1_4					)
      t.put(1_3					)
      t.put(4					)
      t.put(7					)
      t.put(5					)

      print(
          '''
            8
           / \\
          3   10
         / \\    \\
        1   6    14
           / \\   /
          4   7 13
           \\
            5
        '''					)

      print('''Label 6 exists:'''  ,					t.exists(6					)					)
      print('''Label 13 exists:'''  ,					t.exists(1_3					)					)
      print('''Label -1 exists:'''  ,					t.exists(-1					)					)
      print('''Label 12 exists:'''  ,					t.exists(1_2					)					)

      # Prints all the elements of the list in inorder traversal
      _lowerCAmelCase			      =	[i.label for i in t.inorder_traversal()]
      print('''Inorder traversal:'''  ,					_SCREAMING_SNAKE_CASE					)

      # Prints all the elements of the list in preorder traversal
      _lowerCAmelCase			      =	[i.label for i in t.preorder_traversal()]
      print('''Preorder traversal:'''  ,					_SCREAMING_SNAKE_CASE					)

      print('''Max. label:'''  ,					t.get_max_label()					)
      print('''Min. label:'''  ,					t.get_min_label()					)

      # Delete elements
      print('''\nDeleting elements 13, 10, 8, 3, 6, 14'''					)
      print(
          '''
          4
         / \\
        1   7
             \\
              5
        '''					)
      t.remove(1_3					)
      t.remove(1_0					)
      t.remove(8					)
      t.remove(3					)
      t.remove(6					)
      t.remove(1_4					)

      # Prints all the elements of the list in inorder traversal after delete
      _lowerCAmelCase			      =	[i.label for i in t.inorder_traversal()]
      print('''Inorder traversal after delete:'''  ,					_SCREAMING_SNAKE_CASE					)

      # Prints all the elements of the list in preorder traversal after delete
      _lowerCAmelCase			      =	[i.label for i in t.preorder_traversal()]
      print('''Preorder traversal after delete:'''  ,					_SCREAMING_SNAKE_CASE					)

      print('''Max. label:'''  ,					t.get_max_label()					)
      print('''Min. label:'''  ,					t.get_min_label()					)


if __name__ == "__main__":
    binary_search_tree_example()




from __future__ import annotations

from random import randrange
def 				UpperCAmelCase__		(					_SCREAMING_SNAKE_CASE :						list					)->list:
      if len(_SCREAMING_SNAKE_CASE					) < 2:
            return collection
      _lowerCAmelCase			      =	randrange(len(_SCREAMING_SNAKE_CASE					)					)  # Use random element as pivot
      _lowerCAmelCase			      =	collection[pivot_index]
      _lowerCAmelCase			      =	[]  # All elements greater than pivot
      _lowerCAmelCase			      =	[]  # All elements less than or equal to pivot

      for element in collection[:pivot_index]:
            (greater if element > pivot else lesser).append(_SCREAMING_SNAKE_CASE					)

      for element in collection[pivot_index + 1 :]:
            (greater if element > pivot else lesser).append(_SCREAMING_SNAKE_CASE					)

      return [*quick_sort(_SCREAMING_SNAKE_CASE					), pivot, *quick_sort(_SCREAMING_SNAKE_CASE					)]


if __name__ == "__main__":
    UpperCAmelCase_          =				input("Enter numbers separated by a comma:\n").strip()
    UpperCAmelCase_          =				[int(item) for item in user_input.split(",")]
    print(quick_sort(unsorted))