


from __future__ import annotations

import unittest
from collections.abc import Iterator







class  lowerCamelCase__  :





     def __init__(self						,	UpperCAmelCase						,	UpperCAmelCase			)	->  None:
      _lowercase				 =label
      _lowercase				 =parent
      _lowercase				 =None
      _lowercase				 =None







class  lowerCamelCase__  :





     def __init__(self			)	->  None:
      _lowercase				 =None





     def 	__A   (self			)	->  None:
      _lowercase				 =None





     def 	__A   (self			)	->  bool:
      return self.root is None





     def 	__A   (self						,	UpperCAmelCase			)	->  None:
      _lowercase				 =self._put(self.root						,	UpperCAmelCase			)





     def 	__A   (self						,	UpperCAmelCase						,	UpperCAmelCase						,	UpperCAmelCase = None			)	->  Node:
      if node is None:
       _lowercase				 =Node(UpperCAmelCase						,	UpperCAmelCase			)
      else:
       if label < node.label:
        _lowercase				 =self._put(node.left						,	UpperCAmelCase						,	UpperCAmelCase			)
       elif label > node.label:
        _lowercase				 =self._put(node.right						,	UpperCAmelCase						,	UpperCAmelCase			)
       else:
        _lowercase				 =f"Node with label {label} already exists"
        raise Exception(UpperCAmelCase			)

      return node





     def 	__A   (self						,	UpperCAmelCase			)	->  Node:
      return self._search(self.root						,	UpperCAmelCase			)





     def 	__A   (self						,	UpperCAmelCase						,	UpperCAmelCase			)	->  Node:
      if node is None:
       _lowercase				 =f"Node with label {label} does not exist"
       raise Exception(UpperCAmelCase			)
      else:
       if label < node.label:
        _lowercase				 =self._search(node.left						,	UpperCAmelCase			)
       elif label > node.label:
        _lowercase				 =self._search(node.right						,	UpperCAmelCase			)

      return node





     def 	__A   (self						,	UpperCAmelCase			)	->  None:
      _lowercase				 =self.search(UpperCAmelCase			)
      if node.right and node.left:
       _lowercase				 =self._get_lowest_node(node.right			)
       _lowercase				 =node.left
       _lowercase				 =node.right
       _lowercase				 =lowest_node
       if node.right:
        _lowercase				 =lowest_node
       self._reassign_nodes(UpperCAmelCase						,	UpperCAmelCase			)
      elif not node.right and node.left:
       self._reassign_nodes(UpperCAmelCase						,	node.left			)
      elif node.right and not node.left:
       self._reassign_nodes(UpperCAmelCase						,	node.right			)
      else:
       self._reassign_nodes(UpperCAmelCase						,	UpperCAmelCase			)





     def 	__A   (self						,	UpperCAmelCase						,	UpperCAmelCase			)	->  None:
      if new_children:
       _lowercase				 =node.parent

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





     def 	__A   (self						,	UpperCAmelCase			)	->  Node:
      if node.left:
       _lowercase				 =self._get_lowest_node(node.left			)
      else:
       _lowercase				 =node
       self._reassign_nodes(UpperCAmelCase						,	node.right			)

      return lowest_node





     def 	__A   (self						,	UpperCAmelCase			)	->  bool:
      try:
       self.search(UpperCAmelCase			)
       return True
      except Exception:
       return False





     def 	__A   (self			)	->  int:
      if self.root is None:
       raise Exception('''Binary search tree is empty'''			)

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

      return node.label





     def 	__A   (self			)	->  int:
      if self.root is None:
       raise Exception('''Binary search tree is empty'''			)

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

      return node.label





     def 	__A   (self			)	->  Iterator[Node]:
      return self._inorder_traversal(self.root			)





     def 	__A   (self						,	UpperCAmelCase			)	->  Iterator[Node]:
      if node is not None:
       yield from self._inorder_traversal(node.left			)
       yield node
       yield from self._inorder_traversal(node.right			)





     def 	__A   (self			)	->  Iterator[Node]:
      return self._preorder_traversal(self.root			)





     def 	__A   (self						,	UpperCAmelCase			)	->  Iterator[Node]:
      if node is not None:
       yield node
       yield from self._preorder_traversal(node.left			)
       yield from self._preorder_traversal(node.right			)







class  lowerCamelCase__  (			unittest.TestCase):





     @staticmethod
     def 	__A   ()	->  BinarySearchTree:
      _lowercase				 =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			)

      return t





     def 	__A   (self			)	->  None:
      _lowercase				 =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(1_0			)
      assert t.root.right is not None
      assert t.root.right.parent == t.root
      assert t.root.right.label == 1_0

      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(UpperCAmelCase			):  # noqa: B017
       t.put(1			)





     def 	__A   (self			)	->  None:
      _lowercase				 =self._get_binary_search_tree()

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

      _lowercase				 =t.search(1_3			)
      assert node.label == 1_3

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





     def 	__A   (self			)	->  None:
      _lowercase				 =self._get_binary_search_tree()

      t.remove(1_3			)
      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 	__A   (self			)	->  None:
      _lowercase				 =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 	__A   (self			)	->  None:
      _lowercase				 =self._get_binary_search_tree()
      t.empty()
      assert t.root is None





     def 	__A   (self			)	->  None:
      _lowercase				 =self._get_binary_search_tree()
      assert not t.is_empty()

      t.empty()
      assert t.is_empty()





     def 	__A   (self			)	->  None:
      _lowercase				 =self._get_binary_search_tree()

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





     def 	__A   (self			)	->  None:
      _lowercase				 =self._get_binary_search_tree()

      assert t.get_max_label() == 1_4

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





     def 	__A   (self			)	->  None:
      _lowercase				 =self._get_binary_search_tree()

      assert t.get_min_label() == 1

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





     def 	__A   (self			)	->  None:
      _lowercase				 =self._get_binary_search_tree()

      _lowercase				 =[i.label for i in t.inorder_traversal()]
      assert inorder_traversal_nodes == [1, 3, 4, 5, 6, 7, 8, 1_0, 1_3, 1_4]





     def 	__A   (self			)	->  None:
      _lowercase				 =self._get_binary_search_tree()

      _lowercase				 =[i.label for i in t.preorder_traversal()]
      assert preorder_traversal_nodes == [8, 3, 1, 6, 4, 5, 7, 1_0, 1_4, 1_3]



def 							UpperCAmelCase_   (				)	->     None:







 """simple docstring"""


 _lowercase				 =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		)

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

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

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

 # Prints all the elements of the list in preorder traversal
 _lowercase				 =[i.label for i in t.preorder_traversal()]
 print('''Preorder traversal:'''	,		__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(13		)
 t.remove(10		)
 t.remove(8		)
 t.remove(3		)
 t.remove(6		)
 t.remove(14		)

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

 # Prints all the elements of the list in preorder traversal after delete
 _lowercase				 =[i.label for i in t.preorder_traversal()]
 print('''Preorder traversal after delete:'''	,		__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
def 							UpperCAmelCase_   (				__snake_case		)	->     list[int]:







 """simple docstring"""


 if not list_of_ints:
  return []

 if min(__snake_case		) < 0:
  raise ValueError('''All numbers must be positive'''		)

 _lowercase				 =max(len(bin(__snake_case		)[2:]		) for x in list_of_ints		)
 return _msd_radix_sort(__snake_case	,		__snake_case		)
def 							UpperCAmelCase_   (				__snake_case	,		__snake_case		)	->     list[int]:







 """simple docstring"""


 if bit_position == 0 or len(__snake_case		) in [0, 1]:
  return list_of_ints

 _lowercase				 =[]
 _lowercase				 =[]
 # Split numbers based on bit at bit_position from the right
 for number in list_of_ints:
  if (number >> (bit_position - 1)) & 1:
   # number has a one at bit bit_position
   ones.append(__snake_case		)
  else:
   # number has a zero at bit bit_position
   zeros.append(__snake_case		)

    # recursively split both lists further
 _lowercase				 =_msd_radix_sort(__snake_case	,		bit_position - 1		)
 _lowercase				 =_msd_radix_sort(__snake_case	,		bit_position - 1		)

 # recombine lists
 _lowercase				 =zeros
 res.extend(__snake_case		)

 return res
def 							UpperCAmelCase_   (				__snake_case		)	->     List[str]:







 """simple docstring"""


 _lowercase				 =len(__snake_case		)
 if not list_of_ints or length == 1:
  return

 if min(__snake_case		) < 0:
  raise ValueError('''All numbers must be positive'''		)

 _lowercase				 =max(len(bin(__snake_case		)[2:]		) for x in list_of_ints		)
 _msd_radix_sort_inplace(__snake_case	,		__snake_case	,		0	,		__snake_case		)
def 							UpperCAmelCase_   (				__snake_case	,		__snake_case	,		__snake_case	,		__snake_case		)	->     Any:







 """simple docstring"""


 if bit_position == 0 or end_index - begin_index <= 1:
  return

 bit_position -= 1

 _lowercase				 =begin_index
 _lowercase				 =end_index - 1
 while i <= j:
  _lowercase				 =False
  if not (list_of_ints[i] >> bit_position) & 1:
   # found zero at the beginning
   i += 1
   _lowercase				 =True
  if (list_of_ints[j] >> bit_position) & 1:
   # found one at the end
   j -= 1
   _lowercase				 =True

  if changed:
   continue

  _lowercase ,       _lowercase				 =list_of_ints[j], list_of_ints[i]
  j -= 1
  if j != i:
   i += 1

 _msd_radix_sort_inplace(__snake_case	,		__snake_case	,		__snake_case	,		__snake_case		)
 _msd_radix_sort_inplace(__snake_case	,		__snake_case	,		__snake_case	,		__snake_case		)


if __name__ == "__main__":
  import doctest

  doctest.testmod()

