





"""simple docstring"""





from __future__ import annotations

import unittest
from collections.abc import Iterator

class 		lowercase :





      def __init__(	self				,						lowercase				,						lowercase			)		->					None:
            lowerCAmelCase  						=	label
            lowerCAmelCase  						=	parent
            lowerCAmelCase  						=	None
            lowerCAmelCase  						=	None







class 		lowercase :





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





      def    _snake_case      (	self			)		->					None:
            lowerCAmelCase  						=	None





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





      def    _snake_case      (	self				,						lowercase			)		->					None:
            lowerCAmelCase  						=	self._put(self.root				,						lowercase			)





      def    _snake_case      (	self				,						lowercase				,						lowercase				,						lowercase = None			)		->					Node:
            if node is None:
                  lowerCAmelCase  						=	Node(lowercase				,						lowercase			)
            else:
                  if label < node.label:
                        lowerCAmelCase  						=	self._put(node.left				,						lowercase				,						lowercase			)
                  elif label > node.label:
                        lowerCAmelCase  						=	self._put(node.right				,						lowercase				,						lowercase			)
                  else:
                        lowerCAmelCase  						=	f'Node with label {label} already exists'
                        raise Exception(lowercase			)

            return node





      def    _snake_case      (	self				,						lowercase			)		->					Node:
            return self._search(self.root				,						lowercase			)





      def    _snake_case      (	self				,						lowercase				,						lowercase			)		->					Node:
            if node is None:
                  lowerCAmelCase  						=	f'Node with label {label} does not exist'
                  raise Exception(lowercase			)
            else:
                  if label < node.label:
                        lowerCAmelCase  						=	self._search(node.left				,						lowercase			)
                  elif label > node.label:
                        lowerCAmelCase  						=	self._search(node.right				,						lowercase			)

            return node





      def    _snake_case      (	self				,						lowercase			)		->					None:
            lowerCAmelCase  						=	self.search(lowercase			)
            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(lowercase				,						lowercase			)
            elif not node.right and node.left:
                  self._reassign_nodes(lowercase				,						node.left			)
            elif node.right and not node.left:
                  self._reassign_nodes(lowercase				,						node.right			)
            else:
                  self._reassign_nodes(lowercase				,						lowercase			)





      def    _snake_case      (	self				,						lowercase				,						lowercase			)		->					None:
            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    _snake_case      (	self				,						lowercase			)		->					Node:
            if node.left:
                  lowerCAmelCase  						=	self._get_lowest_node(node.left			)
            else:
                  lowerCAmelCase  						=	node
                  self._reassign_nodes(lowercase				,						node.right			)

            return lowest_node





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





      def    _snake_case      (	self			)		->					int:
            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    _snake_case      (	self			)		->					int:
            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    _snake_case      (	self			)		->					Iterator[Node]:
            return self._inorder_traversal(self.root			)





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





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





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







class 		lowercase ( unittest.TestCase ):





      @staticmethod
      def    _snake_case      (	)		->					BinarySearchTree:
            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    _snake_case      (	self			)		->					None:
            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(lowercase			):  # noqa: B017
                  t.put(1			)





      def    _snake_case      (	self			)		->					None:
            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(lowercase			):  # noqa: B017
                  t.search(2			)





      def    _snake_case      (	self			)		->					None:
            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    _snake_case      (	self			)		->					None:
            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    _snake_case      (	self			)		->					None:
            lowerCAmelCase  						=	self._get_binary_search_tree()
            t.empty()
            assert t.root is None





      def    _snake_case      (	self			)		->					None:
            lowerCAmelCase  						=	self._get_binary_search_tree()
            assert not t.is_empty()

            t.empty()
            assert t.is_empty()





      def    _snake_case      (	self			)		->					None:
            lowerCAmelCase  						=	self._get_binary_search_tree()

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





      def    _snake_case      (	self			)		->					None:
            lowerCAmelCase  						=	self._get_binary_search_tree()

            assert t.get_max_label() == 14

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





      def    _snake_case      (	self			)		->					None:
            lowerCAmelCase  						=	self._get_binary_search_tree()

            assert t.get_min_label() == 1

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





      def    _snake_case      (	self			)		->					None:
            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    _snake_case      (	self			)		->					None:
            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__							(  ):







      '''simple docstring'''




      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      )

      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
      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(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
      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()













"""simple docstring"""





import unittest
from dataclasses import dataclass
from typing import Optional

from transformers.utils import ModelOutput

@dataclass
class 		lowercase ( _UpperCAmelCase ):
      _SCREAMING_SNAKE_CASE         =				42
      _SCREAMING_SNAKE_CASE         =				None
      _SCREAMING_SNAKE_CASE         =				None







class 		lowercase ( unittest.TestCase ):





      def    _snake_case      (	self			)		->					Optional[Any]:
            lowerCAmelCase  						=	ModelOutputTest(a=30			)
            self.assertEqual(x.a				,						30			)
            self.assertIsNone(x.b			)
            self.assertIsNone(x.c			)
            with self.assertRaises(lowercase			):
                  lowerCAmelCase  						=	x.d





      def    _snake_case      (	self			)		->					Optional[Any]:
            lowerCAmelCase  						=	ModelOutputTest(a=30				,						b=10			)
            self.assertEqual(x[0]				,						30			)
            self.assertEqual(x[1]				,						10			)
            self.assertEqual(x[:2]				,						(30, 10)			)
            self.assertEqual(x[:]				,						(30, 10)			)

            lowerCAmelCase  						=	ModelOutputTest(a=30				,						c=10			)
            self.assertEqual(x[0]				,						30			)
            self.assertEqual(x[1]				,						10			)
            self.assertEqual(x[:2]				,						(30, 10)			)
            self.assertEqual(x[:]				,						(30, 10)			)





      def    _snake_case      (	self			)		->					Tuple:
            lowerCAmelCase  						=	ModelOutputTest(a=30				,						b=10			)
            self.assertEqual(x["""a"""]				,						30			)
            self.assertEqual(x["""b"""]				,						10			)
            with self.assertRaises(lowercase			):
                  lowerCAmelCase  						=	x["""c"""]

            lowerCAmelCase  						=	ModelOutputTest(a=30				,						c=10			)
            self.assertEqual(x["""a"""]				,						30			)
            self.assertEqual(x["""c"""]				,						10			)
            with self.assertRaises(lowercase			):
                  lowerCAmelCase  						=	x["""b"""]





      def    _snake_case      (	self			)		->					Union[str, Any]:
            lowerCAmelCase  						=	ModelOutputTest(a=30			)
            self.assertEqual(list(x.keys()			)				,						["""a"""]			)
            self.assertEqual(list(x.values()			)				,						[30]			)
            self.assertEqual(list(x.items()			)				,						[("""a""", 30)]			)
            self.assertEqual(list(lowercase			)				,						["""a"""]			)

            lowerCAmelCase  						=	ModelOutputTest(a=30				,						b=10			)
            self.assertEqual(list(x.keys()			)				,						["""a""", """b"""]			)
            self.assertEqual(list(x.values()			)				,						[30, 10]			)
            self.assertEqual(list(x.items()			)				,						[("""a""", 30), ("""b""", 10)]			)
            self.assertEqual(list(lowercase			)				,						["""a""", """b"""]			)

            lowerCAmelCase  						=	ModelOutputTest(a=30				,						c=10			)
            self.assertEqual(list(x.keys()			)				,						["""a""", """c"""]			)
            self.assertEqual(list(x.values()			)				,						[30, 10]			)
            self.assertEqual(list(x.items()			)				,						[("""a""", 30), ("""c""", 10)]			)
            self.assertEqual(list(lowercase			)				,						["""a""", """c"""]			)

            with self.assertRaises(lowercase			):
                  lowerCAmelCase  						=	x.update({"""d""": 20}			)
            with self.assertRaises(lowercase			):
                  del x["a"]
            with self.assertRaises(lowercase			):
                  lowerCAmelCase  						=	x.pop("""a"""			)
            with self.assertRaises(lowercase			):
                  lowerCAmelCase  						=	x.setdefault("""d"""				,						32			)





      def    _snake_case      (	self			)		->					Dict:
            lowerCAmelCase  						=	ModelOutputTest(a=30			)
            lowerCAmelCase  						=	10
            self.assertEqual(x.a				,						10			)
            self.assertEqual(x["""a"""]				,						10			)





      def    _snake_case      (	self			)		->					List[str]:
            lowerCAmelCase  						=	ModelOutputTest(a=30			)
            lowerCAmelCase  						=	10
            self.assertEqual(x.a				,						10			)
            self.assertEqual(x["""a"""]				,						10			)





      def    _snake_case      (	self			)		->					str:
            lowerCAmelCase  						=	ModelOutputTest({"""a""": 30, """b""": 10}			)
            self.assertEqual(list(x.keys()			)				,						["""a""", """b"""]			)
            self.assertEqual(x.a				,						30			)
            self.assertEqual(x.b				,						10			)





      def    _snake_case      (	self			)		->					Dict:
            lowerCAmelCase  						=	ModelOutputTest([("""a""", 30), ("""b""", 10)]			)
            self.assertEqual(list(x.keys()			)				,						["""a""", """b"""]			)
            self.assertEqual(x.a				,						30			)
            self.assertEqual(x.b				,						10			)

            with self.assertRaises(lowercase			):
                  lowerCAmelCase  						=	ModelOutputTest([("""a""", 30), (10, 10)]			)

            lowerCAmelCase  						=	ModelOutputTest(a=(30, 30)			)
            self.assertEqual(list(x.keys()			)				,						["""a"""]			)
            self.assertEqual(x.a				,						(30, 30)			)






