

from collections.abc import Iterable
from typing import Any

class    _lowercase				:

   def __init__(				self	:    Any			,						lowerCamelCase__	:    int | None = None       ) ->			List[str]:
         """simple docstring"""





         A_							       =		value
         A_							       =		None  # Added in order to delete a node easier
         A_							       =		None
         A_							       =		None





   def __repr__(				self	:    Any       ) ->			str:
         """simple docstring"""





         from pprint import pformat

         if self.left is None and self.right is None:
               return str(self.value       )
         return pformat({F"{self.value}": (self.left, self.right)}			,						indent=1       )



class    _lowercase				:

   def __init__(				self	:    Union[str, Any]			,						lowerCamelCase__	:    Node | None = None       ) ->			Tuple:
         """simple docstring"""





         A_							       =		root

   def __str__(				self	:    Optional[int]       ) ->			str:
         """simple docstring"""





         return str(self.root       )

   def     UpperCamelCase					(				self	:    List[str]			,						lowerCamelCase__	:    Node			,						lowerCamelCase__	:    Node | None       ) ->			None:
         """simple docstring"""





         if new_children is not None:  # reset its kids
               A_							       =		node.parent
         if node.parent is not None:  # reset its parent
               if self.is_right(lowerCamelCase__       ):  # If it is the right children
                     A_							       =		new_children
               else:
                     A_							       =		new_children
         else:
               A_							       =		new_children

   def     UpperCamelCase					(				self	:    int			,						lowerCamelCase__	:    Node       ) ->			bool:
         """simple docstring"""





         if node.parent and node.parent.right:
               return node == node.parent.right
         return False

   def     UpperCamelCase					(				self	:    Dict       ) ->			bool:
         """simple docstring"""





         return self.root is None

   def     UpperCamelCase					(				self	:    List[str]			,						lowerCamelCase__	:    List[Any]       ) ->			None:
         """simple docstring"""





         A_							       =		Node(lowerCamelCase__       )  # create a new Node
         if self.empty():  # if Tree is empty
               A_							       =		new_node  # set its root
         else:  # Tree is not empty
               A_							       =		self.root  # from root
               if parent_node is None:
                     return
               while True:  # While we don't get to a leaf
                     if value < parent_node.value:  # We go left
                           if parent_node.left is None:
                                 A_							       =		new_node  # We insert the new node in a leaf
                                 break
                           else:
                                 A_							       =		parent_node.left
                     else:
                           if parent_node.right is None:
                                 A_							       =		new_node
                                 break
                           else:
                                 A_							       =		parent_node.right
               A_							       =		parent_node

   def     UpperCamelCase					(				self	:    Dict			,						*lowerCamelCase__	:    Tuple       ) ->			None:
         """simple docstring"""





         for value in values:
               self.__insert(lowerCamelCase__       )

   def     UpperCamelCase					(				self	:    Optional[int]			,						lowerCamelCase__	:    Union[str, Any]       ) ->			Node | None:
         """simple docstring"""





         if self.empty():
               raise IndexError('''Warning: Tree is empty! please use another.'''       )
         else:
               A_							       =		self.root
               # use lazy evaluation here to avoid NoneType Attribute error
               while node is not None and node.value is not value:
                     A_							       =		node.left if value < node.value else node.right
               return node

   def     UpperCamelCase					(				self	:    List[Any]			,						lowerCamelCase__	:    Node | None = None       ) ->			Node | None:
         """simple docstring"""





         if node is None:
               if self.root is None:
                     return None
               A_							       =		self.root

         if not self.empty():
               while node.right is not None:
                     A_							       =		node.right
         return node

   def     UpperCamelCase					(				self	:    int			,						lowerCamelCase__	:    Node | None = None       ) ->			Node | None:
         """simple docstring"""





         if node is None:
               A_							       =		self.root
         if self.root is None:
               return None
         if not self.empty():
               A_							       =		self.root
               while node.left is not None:
                     A_							       =		node.left
         return node

   def     UpperCamelCase					(				self	:    Optional[int]			,						lowerCamelCase__	:    int       ) ->			None:
         """simple docstring"""





         A_							       =		self.search(lowerCamelCase__       )  # Look for the node with that label
         if node is not None:
               if node.left is None and node.right is None:  # If it has no children
                     self.__reassign_nodes(lowerCamelCase__			,						lowerCamelCase__       )
               elif node.left is None:  # Has only right children
                     self.__reassign_nodes(lowerCamelCase__			,						node.right       )
               elif node.right is None:  # Has only left children
                     self.__reassign_nodes(lowerCamelCase__			,						node.left       )
               else:
                     A_							       =		self.get_max(
                         node.left       )  # Gets the max value of the left branch
                     self.remove(tmp_node.value       )  # type: ignore
                     A_							       =		(
                         tmp_node.value  # type: ignore
                     )  # Assigns the value to the node to delete and keep tree structure

   def     UpperCamelCase					(				self	:    Any			,						lowerCamelCase__	:    Node | None       ) ->			Iterable:
         """simple docstring"""





         if node is not None:
               yield node  # Preorder Traversal
               yield from self.preorder_traverse(node.left       )
               yield from self.preorder_traverse(node.right       )

   def     UpperCamelCase					(				self	:    int			,						lowerCamelCase__	:    List[str]=None       ) ->			Any:
         """simple docstring"""





         if traversal_function is None:
               return self.preorder_traverse(self.root       )
         else:
               return traversal_function(self.root       )

   def     UpperCamelCase					(				self	:    Optional[int]			,						lowerCamelCase__	:    list			,						lowerCamelCase__	:    Node | None       ) ->			None:
         """simple docstring"""





         if node:
               self.inorder(lowerCamelCase__			,						node.left       )
               arr.append(node.value       )
               self.inorder(lowerCamelCase__			,						node.right       )





   def     UpperCamelCase					(				self	:    Dict			,						lowerCamelCase__	:    int			,						lowerCamelCase__	:    Node       ) ->			int:
         """simple docstring"""





         A_							       =		[]
         self.inorder(lowerCamelCase__			,						lowerCamelCase__       )  # append all values to list using inorder traversal
         return arr[k - 1]







def 							_lowerCamelCase   (			SCREAMING_SNAKE_CASE   ):
      '''simple docstring'''







      A_							       =		[]
      if curr_node is not None:
            A_							       =		postorder(curr_node.left   ) + postorder(curr_node.right   ) + [curr_node]
      return node_list







def 							_lowerCamelCase   (			):
      '''simple docstring'''







      A_							       =		(8, 3, 6, 1, 10, 14, 13, 4, 7)
      A_							       =		BinarySearchTree()
      for i in testlist:
            t.insert(SCREAMING_SNAKE_CASE   )

      # Prints all the elements of the list in order traversal
      print(SCREAMING_SNAKE_CASE   )

      if t.search(6   ) is not None:
            print('''The value 6 exists'''   )
      else:
            print('''The value 6 doesn\'t exist'''   )

      if t.search(-1   ) is not None:
            print('''The value -1 exists'''   )
      else:
            print('''The value -1 doesn\'t exist'''   )

      if not t.empty():
            print('''Max Value: '''		,				t.get_max().value   )  # type: ignore
            print('''Min Value: '''		,				t.get_min().value   )  # type: ignore

      for i in testlist:
            t.remove(SCREAMING_SNAKE_CASE   )
            print(SCREAMING_SNAKE_CASE   )


if __name__ == "__main__":
      import doctest

      doctest.testmod(verbose=True)








# this script reports modified .py files under the desired list of top-level sub-dirs passed as a list of arguments, e.g.:
#   python ./utils/get_modified_files.py utils src tests examples
#
# it uses git to find the forking point and which files were modified - i.e. files not under git won't be considered
# since the output of this script is fed into Makefile commands it doesn't print a newline after the results

import re
import subprocess
import sys


__lowercase				      =						subprocess.check_output("""git merge-base main HEAD""".split()).decode("""utf-8""")
__lowercase				      =						(
    subprocess.check_output(f'git diff --diff-filter=d --name-only {fork_point_sha}'.split()).decode("""utf-8""").split()
)

__lowercase				      =						"""|""".join(sys.argv[1:])
__lowercase				      =						re.compile(rf'^({joined_dirs}).*?\.py$')

__lowercase				      =						[x for x in modified_files if regex.match(x)]
print(""" """.join(relevant_modified_files), end="""""")





