code: 
  
  
  """simple docstring"""
  from __future__ import annotations
  
  import unittest
  from collections.abc import Iterator
  
  
  
  
  class   lowercase__							:
  
  
  
  
  
     def __init__(       self			,      SCREAMING_SNAKE_CASE			,      SCREAMING_SNAKE_CASE)     ->     None:
        _lowerCamelCase  :				Any      =		label
        _lowerCamelCase  :				Optional[Any]      =		parent
        _lowerCamelCase  :				Node | None      =		None
        _lowerCamelCase  :				Node | None      =		None
  
  
  
  
  
  
  
  class   lowercase__							:
  
  
  
  
  
     def __init__(       self)     ->     None:
        _lowerCamelCase  :				Node | None      =		None
  
  
  
  
  
     def 		UpperCamelCase_     (       self)     ->     None:
        _lowerCamelCase  :				Tuple      =		None
  
  
  
  
  
     def 		UpperCamelCase_     (       self)     ->     bool:
        return self.root is None
  
  
  
  
  
     def 		UpperCamelCase_     (       self			,      SCREAMING_SNAKE_CASE)     ->     None:
        _lowerCamelCase  :				List[Any]      =		self._put(self.root			,      SCREAMING_SNAKE_CASE)
  
  
  
  
  
     def 		UpperCamelCase_     (       self			,      SCREAMING_SNAKE_CASE			,      SCREAMING_SNAKE_CASE			,      SCREAMING_SNAKE_CASE = None)     ->     Node:
        if node is None:
           _lowerCamelCase  :				List[Any]      =		Node(SCREAMING_SNAKE_CASE			,      SCREAMING_SNAKE_CASE)
        else:
           if label < node.label:
              _lowerCamelCase  :				Optional[int]      =		self._put(node.left			,      SCREAMING_SNAKE_CASE			,      SCREAMING_SNAKE_CASE)
           elif label > node.label:
              _lowerCamelCase  :				List[str]      =		self._put(node.right			,      SCREAMING_SNAKE_CASE			,      SCREAMING_SNAKE_CASE)
           else:
              _lowerCamelCase  :				int      =		F'Node with label {label} already exists'
              raise Exception(SCREAMING_SNAKE_CASE)
  
        return node
  
  
  
  
  
     def 		UpperCamelCase_     (       self			,      SCREAMING_SNAKE_CASE)     ->     Node:
        return self._search(self.root			,      SCREAMING_SNAKE_CASE)
  
  
  
  
  
     def 		UpperCamelCase_     (       self			,      SCREAMING_SNAKE_CASE			,      SCREAMING_SNAKE_CASE)     ->     Node:
        if node is None:
           _lowerCamelCase  :				Optional[Any]      =		F'Node with label {label} does not exist'
           raise Exception(SCREAMING_SNAKE_CASE)
        else:
           if label < node.label:
              _lowerCamelCase  :				Union[str, Any]      =		self._search(node.left			,      SCREAMING_SNAKE_CASE)
           elif label > node.label:
              _lowerCamelCase  :				Any      =		self._search(node.right			,      SCREAMING_SNAKE_CASE)
  
        return node
  
  
  
  
  
     def 		UpperCamelCase_     (       self			,      SCREAMING_SNAKE_CASE)     ->     None:
        _lowerCamelCase  :				Tuple      =		self.search(SCREAMING_SNAKE_CASE)
        if node.right and node.left:
           _lowerCamelCase  :				List[str]      =		self._get_lowest_node(node.right)
           _lowerCamelCase  :				Optional[int]      =		node.left
           _lowerCamelCase  :				Dict      =		node.right
           _lowerCamelCase  :				Any      =		lowest_node
           if node.right:
              _lowerCamelCase  :				Dict      =		lowest_node
           self._reassign_nodes(SCREAMING_SNAKE_CASE			,      SCREAMING_SNAKE_CASE)
        elif not node.right and node.left:
           self._reassign_nodes(SCREAMING_SNAKE_CASE			,      node.left)
        elif node.right and not node.left:
           self._reassign_nodes(SCREAMING_SNAKE_CASE			,      node.right)
        else:
           self._reassign_nodes(SCREAMING_SNAKE_CASE			,      SCREAMING_SNAKE_CASE)
  
  
  
  
  
     def 		UpperCamelCase_     (       self			,      SCREAMING_SNAKE_CASE			,      SCREAMING_SNAKE_CASE)     ->     None:
        if new_children:
           _lowerCamelCase  :				Optional[Any]      =		node.parent
  
        if node.parent:
           if node.parent.right == node:
              _lowerCamelCase  :				Optional[Any]      =		new_children
           else:
              _lowerCamelCase  :				Union[str, Any]      =		new_children
        else:
           _lowerCamelCase  :				Tuple      =		new_children
  
  
  
  
  
     def 		UpperCamelCase_     (       self			,      SCREAMING_SNAKE_CASE)     ->     Node:
        if node.left:
           _lowerCamelCase  :				int      =		self._get_lowest_node(node.left)
        else:
           _lowerCamelCase  :				int      =		node
           self._reassign_nodes(SCREAMING_SNAKE_CASE			,      node.right)
  
        return lowest_node
  
  
  
  
  
     def 		UpperCamelCase_     (       self			,      SCREAMING_SNAKE_CASE)     ->     bool:
        try:
           self.search(SCREAMING_SNAKE_CASE)
           return True
        except Exception:
           return False
  
  
  
  
  
     def 		UpperCamelCase_     (       self)     ->     int:
        if self.root is None:
           raise Exception("""Binary search tree is empty""")
  
        _lowerCamelCase  :				Optional[Any]      =		self.root
        while node.right is not None:
           _lowerCamelCase  :				int      =		node.right
  
        return node.label
  
  
  
  
  
     def 		UpperCamelCase_     (       self)     ->     int:
        if self.root is None:
           raise Exception("""Binary search tree is empty""")
  
        _lowerCamelCase  :				Optional[Any]      =		self.root
        while node.left is not None:
           _lowerCamelCase  :				List[str]      =		node.left
  
        return node.label
  
  
  
  
  
     def 		UpperCamelCase_     (       self)     ->     Iterator[Node]:
        return self._inorder_traversal(self.root)
  
  
  
  
  
     def 		UpperCamelCase_     (       self			,      SCREAMING_SNAKE_CASE)     ->     Iterator[Node]:
        if node is not None:
           yield from self._inorder_traversal(node.left)
           yield node
           yield from self._inorder_traversal(node.right)
  
  
  
  
  
     def 		UpperCamelCase_     (       self)     ->     Iterator[Node]:
        return self._preorder_traversal(self.root)
  
  
  
  
  
     def 		UpperCamelCase_     (       self			,      SCREAMING_SNAKE_CASE)     ->     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 		UpperCamelCase_     (       )     ->     BinarySearchTree:
        _lowerCamelCase  :				List[Any]      =		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 		UpperCamelCase_     (       self)     ->     None:
        _lowerCamelCase  :				Optional[int]      =		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(SCREAMING_SNAKE_CASE):  # noqa: B017
           t.put(1)
  
  
  
  
  
     def 		UpperCamelCase_     (       self)     ->     None:
        _lowerCamelCase  :				List[str]      =		self._get_binary_search_tree()
  
        _lowerCamelCase  :				Union[str, Any]      =		t.search(6)
        assert node.label == 6
  
        _lowerCamelCase  :				Optional[Any]      =		t.search(13)
        assert node.label == 13
  
        with self.assertRaises(SCREAMING_SNAKE_CASE):  # noqa: B017
           t.search(2)
  
  
  
  
  
     def 		UpperCamelCase_     (       self)     ->     None:
        _lowerCamelCase  :				List[str]      =		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 		UpperCamelCase_     (       self)     ->     None:
        _lowerCamelCase  :				Any      =		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 		UpperCamelCase_     (       self)     ->     None:
        _lowerCamelCase  :				str      =		self._get_binary_search_tree()
        t.empty()
        assert t.root is None
  
  
  
  
  
     def 		UpperCamelCase_     (       self)     ->     None:
        _lowerCamelCase  :				Optional[Any]      =		self._get_binary_search_tree()
        assert not t.is_empty()
  
        t.empty()
        assert t.is_empty()
  
  
  
  
  
     def 		UpperCamelCase_     (       self)     ->     None:
        _lowerCamelCase  :				Dict      =		self._get_binary_search_tree()
  
        assert t.exists(6)
        assert not t.exists(-1)
  
  
  
  
  
     def 		UpperCamelCase_     (       self)     ->     None:
        _lowerCamelCase  :				str      =		self._get_binary_search_tree()
  
        assert t.get_max_label() == 14
  
        t.empty()
        with self.assertRaises(SCREAMING_SNAKE_CASE):  # noqa: B017
           t.get_max_label()
  
  
  
  
  
     def 		UpperCamelCase_     (       self)     ->     None:
        _lowerCamelCase  :				Dict      =		self._get_binary_search_tree()
  
        assert t.get_min_label() == 1
  
        t.empty()
        with self.assertRaises(SCREAMING_SNAKE_CASE):  # noqa: B017
           t.get_min_label()
  
  
  
  
  
     def 		UpperCamelCase_     (       self)     ->     None:
        _lowerCamelCase  :				List[Any]      =		self._get_binary_search_tree()
  
        _lowerCamelCase  :				Any      =		[i.label for i in t.inorder_traversal()]
        assert inorder_traversal_nodes == [1, 3, 4, 5, 6, 7, 8, 10, 13, 14]
  
  
  
  
  
     def 		UpperCamelCase_     (       self)     ->     None:
        _lowerCamelCase  :				Union[str, Any]      =		self._get_binary_search_tree()
  
        _lowerCamelCase  :				Optional[Any]      =		[i.label for i in t.preorder_traversal()]
        assert preorder_traversal_nodes == [8, 3, 1, 6, 4, 5, 7, 10, 14, 13]
  
  
  
  
  
  
  
  def 							_snake_case			(      ):
  
  
  
  
     """simple docstring"""
  
  
  
  
  
  
  
     _lowerCamelCase  :				Any      =		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  :				int      =		[i.label for i in t.inorder_traversal()]
     print("""Inorder traversal:"""	,   __snake_case      )
  
     # Prints all the elements of the list in preorder traversal
     _lowerCamelCase  :				int      =		[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
     _lowerCamelCase  :				Any      =		[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
     _lowerCamelCase  :				str      =		[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()
  
  
style_context: 
  
  
  """simple docstring"""
  import itertools
  from dataclasses import dataclass
  from io import StringIO
  from typing import Optional
  
  import pyarrow as pa
  
  import datasets
  from datasets.features.features import require_storage_cast
  from datasets.table import table_cast
  
  
  UpperCAmelCase   =	datasets.utils.logging.get_logger(__name__)
  
  
  
  
  @dataclass
  class   lowercase__							(				datasets.BuilderConfig							):
     __UpperCAmelCase       					=				None
     __UpperCAmelCase       					=				"utf-8"
     __UpperCAmelCase       					=				None
     __UpperCAmelCase       					=				10 << 20  # 10MB
     __UpperCAmelCase       					=				False
     __UpperCAmelCase       					=				"line"
  
  
  
  
  
  
  
  class   lowercase__							(				datasets.ArrowBasedBuilder							):
     __UpperCAmelCase       					=				TextConfig
  
  
  
  
  
     def 		UpperCamelCase_     (       self)     ->     int:
        return datasets.DatasetInfo(features=self.config.features)
  
  
  
  
  
     def 		UpperCamelCase_     (       self			,      SCREAMING_SNAKE_CASE)     ->     Optional[int]:
        if not self.config.data_files:
           raise ValueError(F'At least one data file must be specified, but got data_files={self.config.data_files}')
        _lowerCamelCase  :				Dict      =		dl_manager.download_and_extract(self.config.data_files)
        if isinstance(SCREAMING_SNAKE_CASE			,      (str, list, tuple)):
           _lowerCamelCase  :				Optional[Any]      =		data_files
           if isinstance(SCREAMING_SNAKE_CASE			,      SCREAMING_SNAKE_CASE):
              _lowerCamelCase  :				List[Any]      =		[files]
           _lowerCamelCase  :				List[str]      =		[dl_manager.iter_files(SCREAMING_SNAKE_CASE) for file in files]
           return [datasets.SplitGenerator(name=datasets.Split.TRAIN			,      gen_kwargs={"""files""": files})]
        _lowerCamelCase  :				int      =		[]
        for split_name, files in data_files.items():
           if isinstance(SCREAMING_SNAKE_CASE			,      SCREAMING_SNAKE_CASE):
              _lowerCamelCase  :				Any      =		[files]
           _lowerCamelCase  :				Any      =		[dl_manager.iter_files(SCREAMING_SNAKE_CASE) for file in files]
           splits.append(datasets.SplitGenerator(name=SCREAMING_SNAKE_CASE			,      gen_kwargs={"""files""": files}))
        return splits
  
  
  
  
  
     def 		UpperCamelCase_     (       self			,      SCREAMING_SNAKE_CASE)     ->     pa.Table:
        if self.config.features is not None:
           _lowerCamelCase  :				Union[str, Any]      =		self.config.features.arrow_schema
           if all(not require_storage_cast(SCREAMING_SNAKE_CASE) for feature in self.config.features.values()):
              # cheaper cast
              _lowerCamelCase  :				Any      =		pa_table.cast(SCREAMING_SNAKE_CASE)
           else:
              # more expensive cast; allows str <-> int/float or str to Audio for example
              _lowerCamelCase  :				Any      =		table_cast(SCREAMING_SNAKE_CASE			,      SCREAMING_SNAKE_CASE)
           return pa_table
        else:
           return pa_table.cast(pa.schema({"""text""": pa.string()}))
  
  
  
  
  
     def 		UpperCamelCase_     (       self			,      SCREAMING_SNAKE_CASE)     ->     Any:
        _lowerCamelCase  :				Optional[Any]      =		list(self.config.features) if self.config.features is not None else ["""text"""]
        for file_idx, file in enumerate(itertools.chain.from_iterable(SCREAMING_SNAKE_CASE)):
           # open in text mode, by default translates universal newlines ("\n", "\r\n" and "\r") into "\n"
           with open(SCREAMING_SNAKE_CASE			,      encoding=self.config.encoding			,      errors=self.config.errors) as f:
              if self.config.sample_by == "line":
                 _lowerCamelCase  :				Union[str, Any]      =		0
                 while True:
                    _lowerCamelCase  :				int      =		f.read(self.config.chunksize)
                    if not batch:
                       break
                    batch += f.readline()  # finish current line
                    # StringIO.readlines, by default splits only on "\n" (and keeps line breaks)
                    _lowerCamelCase  :				List[str]      =		StringIO(SCREAMING_SNAKE_CASE).readlines()
                    if not self.config.keep_linebreaks:
                       _lowerCamelCase  :				Optional[Any]      =		[line.rstrip("""\n""") for line in batch]
                    _lowerCamelCase  :				Any      =		pa.Table.from_arrays([pa.array(SCREAMING_SNAKE_CASE)]			,      names=SCREAMING_SNAKE_CASE)
                    # Uncomment for debugging (will print the Arrow table size and elements)
                    # logger.warning(f"pa_table: {pa_table} num rows: {pa_table.num_rows}")
                    # logger.warning('\n'.join(str(pa_table.slice(i, 1).to_pydict()) for i in range(pa_table.num_rows)))
                    yield (file_idx, batch_idx), self._cast_table(SCREAMING_SNAKE_CASE)
                    batch_idx += 1
              elif self.config.sample_by == "paragraph":
                 _lowerCamelCase  :				Optional[Any]      =		0
                 _lowerCamelCase  :				Dict      =		""""""
                 while True:
                    _lowerCamelCase  :				Union[str, Any]      =		f.read(self.config.chunksize)
                    if not new_batch:
                       break
                    batch += new_batch
                    batch += f.readline()  # finish current line
                    _lowerCamelCase  :				Any      =		batch.split("""\n\n""")
                    _lowerCamelCase  :				Dict      =		pa.Table.from_arrays(
                        [pa.array([example for example in batch[:-1] if example])]			,      names=SCREAMING_SNAKE_CASE)
                    # Uncomment for debugging (will print the Arrow table size and elements)
                    # logger.warning(f"pa_table: {pa_table} num rows: {pa_table.num_rows}")
                    # logger.warning('\n'.join(str(pa_table.slice(i, 1).to_pydict()) for i in range(pa_table.num_rows)))
                    yield (file_idx, batch_idx), self._cast_table(SCREAMING_SNAKE_CASE)
                    batch_idx += 1
                    _lowerCamelCase  :				Union[str, Any]      =		batch[-1]
                 if batch:
                    _lowerCamelCase  :				Optional[int]      =		pa.Table.from_arrays([pa.array([batch])]			,      names=SCREAMING_SNAKE_CASE)
                    yield (file_idx, batch_idx), self._cast_table(SCREAMING_SNAKE_CASE)
              elif self.config.sample_by == "document":
                 _lowerCamelCase  :				Tuple      =		f.read()
                 _lowerCamelCase  :				List[Any]      =		pa.Table.from_arrays([pa.array([text])]			,      names=SCREAMING_SNAKE_CASE)
                 yield file_idx, self._cast_table(SCREAMING_SNAKE_CASE)
  
  