





from collections.abc import Iterable
from typing import Any
class      UpperCamelCase_						:




					def __init__(						self			,  lowerCAmelCase_ = None					)						->							str:
										_snake_case													=			value
										_snake_case													=			None  # Added in order to delete a node easier
										_snake_case													=			None
										_snake_case													=			None






					def __repr__(						self					)						->							str:
										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      UpperCamelCase_						:




					def __init__(						self			,  lowerCAmelCase_ = None					)						->							Dict:
										_snake_case													=			root




					def __str__(						self					)						->							str:
										return str(self.root					)




					def 		lowerCAmelCase     (						self			,  lowerCAmelCase_			,  lowerCAmelCase_					)						->							None:
										if new_children is not None:  # reset its kids
															_snake_case													=			node.parent
										if node.parent is not None:  # reset its parent
															if self.is_right(lowerCAmelCase_					):  # If it is the right children
																				_snake_case													=			new_children
															else:
																				_snake_case													=			new_children
										else:
															_snake_case													=			new_children




					def 		lowerCAmelCase     (						self			,  lowerCAmelCase_					)						->							bool:
										if node.parent and node.parent.right:
															return node == node.parent.right
										return False




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




					def 		lowerCAmelCase     (						self			,  lowerCAmelCase_					)						->							None:
										_snake_case													=			Node(lowerCAmelCase_					)  # create a new Node
										if self.empty():  # if Tree is empty
															_snake_case													=			new_node  # set its root
										else:  # Tree is not empty
															_snake_case													=			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:
																														_snake_case													=			new_node  # We insert the new node in a leaf
																														break
																									else:
																														_snake_case													=			parent_node.left
																				else:
																									if parent_node.right is None:
																														_snake_case													=			new_node
																														break
																									else:
																														_snake_case													=			parent_node.right
															_snake_case													=			parent_node




					def 		lowerCAmelCase     (						self			,  *lowerCAmelCase_					)						->							None:
										for value in values:
															self.__insert(lowerCAmelCase_					)




					def 		lowerCAmelCase     (						self			,  lowerCAmelCase_					)						->							Node | None:
										if self.empty():
															raise IndexError('Warning: Tree is empty! please use another.'					)
										else:
															_snake_case													=			self.root
															# use lazy evaluation here to avoid NoneType Attribute error
															while node is not None and node.value is not value:
																				_snake_case													=			node.left if value < node.value else node.right
															return node




					def 		lowerCAmelCase     (						self			,  lowerCAmelCase_ = None					)						->							Node | None:
										if node is None:
															if self.root is None:
																				return None
															_snake_case													=			self.root

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




					def 		lowerCAmelCase     (						self			,  lowerCAmelCase_ = None					)						->							Node | None:
										if node is None:
															_snake_case													=			self.root
										if self.root is None:
															return None
										if not self.empty():
															_snake_case													=			self.root
															while node.left is not None:
																				_snake_case													=			node.left
										return node




					def 		lowerCAmelCase     (						self			,  lowerCAmelCase_					)						->							None:
										_snake_case													=			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:
																				_snake_case													=			self.get_max(
																				    node.left					)  # Gets the max value of the left branch
																				self.remove(tmp_node.value					)  # type: ignore
																				_snake_case													=			(
																				    tmp_node.value  # type: ignore
																				)  # Assigns the value to the node to delete and keep tree structure




					def 		lowerCAmelCase     (						self			,  lowerCAmelCase_					)						->							Iterable:
										if node is not None:
															yield node  # Preorder Traversal
															yield from self.preorder_traverse(node.left					)
															yield from self.preorder_traverse(node.right					)




					def 		lowerCAmelCase     (						self			,  lowerCAmelCase_=None					)						->							Any:
										if traversal_function is None:
															return self.preorder_traverse(self.root					)
										else:
															return traversal_function(self.root					)




					def 		lowerCAmelCase     (						self			,  lowerCAmelCase_			,  lowerCAmelCase_					)						->							None:
										if node:
															self.inorder(lowerCAmelCase_			,  node.left					)
															arr.append(node.value					)
															self.inorder(lowerCAmelCase_			,  node.right					)






					def 		lowerCAmelCase     (						self			,  lowerCAmelCase_			,  lowerCAmelCase_					)						->							int:
										_snake_case													=			[]
										self.inorder(lowerCAmelCase_			,  lowerCAmelCase_					)  # append all values to list using inorder traversal
										return arr[k - 1]





def   lowerCamelCase__       (       UpperCamelCase__     :    Node | None  )     ->	list[Node]:



					'''simple docstring'''




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





def   lowerCamelCase__       (       )     ->	None:



					'''simple docstring'''




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

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

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


if __name__ == "__main__":
					import doctest

					doctest.testmod(verbose=True)










from collections.abc import Sequence





def   lowerCamelCase__       (       UpperCamelCase__     :    Sequence[float]    ,      UpperCamelCase__     :    bool = False  )     ->	float:



					'''simple docstring'''




					if not arr:
										return 0

					_snake_case													=			0 if allow_empty_subarrays else float('-inf'  )
					_snake_case													=			0.0
					for num in arr:
										_snake_case													=			max(0 if allow_empty_subarrays else num    ,      curr_sum + num  )
										_snake_case													=			max(UpperCamelCase__    ,      UpperCamelCase__  )

					return max_sum


if __name__ == "__main__":
					from doctest import testmod

					testmod()

					UpperCAmelCase_ 							=       [-2, 1, -3, 4, -1, 2, 1, -5, 4]
					print(F"{max_subarray_sum(nums) = }")



