






from collections.abc import Iterable
from typing import Any

class 							SCREAMING_SNAKE_CASE__		:





					"""simple docstring"""






					def __init__(      self  :						Optional[Any]							,	__A  :						int | None = None ):
						snake_case__				:   Dict     =						value
						snake_case__				:   Node | None     =						None  # Added in order to delete a node easier
						snake_case__				:   Node | None     =						None
						snake_case__				:   Node | None     =						None






					def __repr__(      self  :						List[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 							SCREAMING_SNAKE_CASE__		:





					"""simple docstring"""






					def __init__(      self  :						Tuple							,	__A  :						Node | None = None ):
						snake_case__				:   Union[str, Any]     =						root



					def __str__(      self  :						Optional[int] ):
						return str(self.root )



					def  _lowercase  (      self  :						Dict							,	__A  :						Node							,	__A  :						Node | None ):
						if new_children is not None:  # reset its kids
							snake_case__				:   Any     =						node.parent
						if node.parent is not None:  # reset its parent
							if self.is_right(__A ):  # If it is the right children
								snake_case__				:   List[str]     =						new_children
							else:
								snake_case__				:   Dict     =						new_children
						else:
							snake_case__				:   Union[str, Any]     =						new_children



					def  _lowercase  (      self  :						Tuple							,	__A  :						Node ):
						if node.parent and node.parent.right:
							return node == node.parent.right
						return False



					def  _lowercase  (      self  :						List[Any] ):
						return self.root is None



					def  _lowercase  (      self  :						Dict							,	__A  :						Optional[int] ):
						snake_case__				:   List[str]     =						Node(__A )  # create a new Node
						if self.empty():  # if Tree is empty
							snake_case__				:   List[str]     =						new_node  # set its root
						else:  # Tree is not empty
							snake_case__				:   Any     =						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__				:   Optional[int]     =						new_node  # We insert the new node in a leaf
										break
									else:
										snake_case__				:   int     =						parent_node.left
								else:
									if parent_node.right is None:
										snake_case__				:   Union[str, Any]     =						new_node
										break
									else:
										snake_case__				:   Dict     =						parent_node.right
							snake_case__				:   int     =						parent_node



					def  _lowercase  (      self  :						Optional[Any]							,	*__A  :						Tuple ):
						for value in values:
							self.__insert(__A )



					def  _lowercase  (      self  :						List[str]							,	__A  :						List[Any] ):
						if self.empty():
							raise IndexError("Warning: Tree is empty! please use another." )
						else:
							snake_case__				:   str     =						self.root
							# use lazy evaluation here to avoid NoneType Attribute error
							while node is not None and node.value is not value:
								snake_case__				:   List[Any]     =						node.left if value < node.value else node.right
							return node



					def  _lowercase  (      self  :						Dict							,	__A  :						Node | None = None ):
						if node is None:
							if self.root is None:
								return None
							snake_case__				:   List[Any]     =						self.root

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



					def  _lowercase  (      self  :						Union[str, Any]							,	__A  :						Node | None = None ):
						if node is None:
							snake_case__				:   str     =						self.root
						if self.root is None:
							return None
						if not self.empty():
							snake_case__				:   int     =						self.root
							while node.left is not None:
								snake_case__				:   str     =						node.left
						return node



					def  _lowercase  (      self  :						Tuple							,	__A  :						int ):
						snake_case__				:   Tuple     =						self.search(__A )  # 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(__A							,	__A )
							elif node.left is None:  # Has only right children
								self.__reassign_nodes(__A							,	node.right )
							elif node.right is None:  # Has only left children
								self.__reassign_nodes(__A							,	node.left )
							else:
								snake_case__				:   Any     =						self.get_max(
								    node.left )  # Gets the max value of the left branch
								self.remove(tmp_node.value )  # type: ignore
								snake_case__				:   int     =						(
								    tmp_node.value  # type: ignore
								)  # Assigns the value to the node to delete and keep tree structure



					def  _lowercase  (      self  :						Dict							,	__A  :						Node | None ):
						if node is not None:
							yield node  # Preorder Traversal
							yield from self.preorder_traverse(node.left )
							yield from self.preorder_traverse(node.right )



					def  _lowercase  (      self  :						Optional[int]							,	__A  :						Optional[int]=None ):
						if traversal_function is None:
							return self.preorder_traverse(self.root )
						else:
							return traversal_function(self.root )



					def  _lowercase  (      self  :						Optional[int]							,	__A  :						list							,	__A  :						Node | None ):
						if node:
							self.inorder(__A							,	node.left )
							arr.append(node.value )
							self.inorder(__A							,	node.right )






					def  _lowercase  (      self  :						str							,	__A  :						int							,	__A  :						Node ):
						snake_case__				:   list[int]     =						[]
						self.inorder(__A							,	__A )  # append all values to list using inorder traversal
						return arr[k - 1]







def   SCREAMING_SNAKE_CASE       (				snake_case_      :							Node | None     ):
	snake_case__				:   Union[str, Any]     =						[]
	if curr_node is not None:
		snake_case__				:   Union[str, Any]     =						postorder(curr_node.left     ) + postorder(curr_node.right     ) + [curr_node]
	return node_list







def   SCREAMING_SNAKE_CASE       (				):
	snake_case__				:   Any     =						(8, 3, 6, 1, 10, 14, 13, 4, 7)
	snake_case__				:   int     =						BinarySearchTree()
	for i in testlist:
		t.insert(snake_case_     )

	# Prints all the elements of the list in order traversal
	print(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(snake_case_     )
		print(snake_case_     )


if __name__ == "__main__":
	import doctest

	doctest.testmod(verbose=True)











from __future__ import annotations

import time

__lowerCamelCase      :    str   		=   list[tuple[int, int]]

__lowerCamelCase      :    Optional[int]   		=   [
    [0, 0, 0, 0, 0, 0, 0],
    [0, 1, 0, 0, 0, 0, 0],  # 0 are free path whereas 1's are obstacles
    [0, 0, 0, 0, 0, 0, 0],
    [0, 0, 1, 0, 0, 0, 0],
    [1, 0, 1, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 1, 0, 0],
]

__lowerCamelCase      :    Tuple   		=   [[-1, 0], [0, -1], [1, 0], [0, 1]]  # up, left, down, right



class 							SCREAMING_SNAKE_CASE__		:





					"""simple docstring"""






					def __init__(      self  :						Union[str, Any]							,	__A  :						int							,	__A  :						int							,	__A  :						int							,	__A  :						int							,	__A  :						Node | None ):
						snake_case__				:   Optional[int]     =						pos_x
						snake_case__				:   Dict     =						pos_y
						snake_case__				:   int     =						(pos_y, pos_x)
						snake_case__				:   Optional[int]     =						goal_x
						snake_case__				:   Tuple     =						goal_y
						snake_case__				:   str     =						parent



class 							SCREAMING_SNAKE_CASE__		:





					"""simple docstring"""






					def __init__(      self  :						List[Any]							,	__A  :						tuple[int, int]							,	__A  :						tuple[int, int] ):
						snake_case__				:   Tuple     =						Node(start[1]							,	start[0]							,	goal[1]							,	goal[0]							,	__A )
						snake_case__				:   Tuple     =						Node(goal[1]							,	goal[0]							,	goal[1]							,	goal[0]							,	__A )

						snake_case__				:   int     =						[self.start]
						snake_case__				:   Union[str, Any]     =						False



					def  _lowercase  (      self  :						Dict ):
						while self.node_queue:
							snake_case__				:   Optional[Any]     =						self.node_queue.pop(0 )

							if current_node.pos == self.target.pos:
								snake_case__				:   Optional[Any]     =						True
								return self.retrace_path(__A )

							snake_case__				:   int     =						self.get_successors(__A )

							for node in successors:
								self.node_queue.append(__A )

						if not self.reached:
							return [self.start.pos]
						return None



					def  _lowercase  (      self  :						Union[str, Any]							,	__A  :						Node ):
						snake_case__				:   str     =						[]
						for action in delta:
							snake_case__				:   str     =						parent.pos_x + action[1]
							snake_case__				:   Union[str, Any]     =						parent.pos_y + action[0]
							if not (0 <= pos_x <= len(grid[0] ) - 1 and 0 <= pos_y <= len(__A ) - 1):
								continue

							if grid[pos_y][pos_x] != 0:
								continue

							successors.append(
							    Node(__A							,	__A							,	self.target.pos_y							,	self.target.pos_x							,	__A ) )
						return successors






					def  _lowercase  (      self  :						Optional[Any]							,	__A  :						Node | None ):
						snake_case__				:   Tuple     =						node
						snake_case__				:   Any     =						[]
						while current_node is not None:
							path.append((current_node.pos_y, current_node.pos_x) )
							snake_case__				:   Tuple     =						current_node.parent
						path.reverse()
						return path



class 							SCREAMING_SNAKE_CASE__		:





					"""simple docstring"""






					def __init__(      self  :						Dict							,	__A  :						str							,	__A  :						int ):
						snake_case__				:   str     =						BreadthFirstSearch(__A							,	__A )
						snake_case__				:   int     =						BreadthFirstSearch(__A							,	__A )
						snake_case__				:   Tuple     =						False



					def  _lowercase  (      self  :						Optional[Any] ):
						while self.fwd_bfs.node_queue or self.bwd_bfs.node_queue:
							snake_case__				:   Any     =						self.fwd_bfs.node_queue.pop(0 )
							snake_case__				:   List[str]     =						self.bwd_bfs.node_queue.pop(0 )

							if current_bwd_node.pos == current_fwd_node.pos:
								snake_case__				:   List[str]     =						True
								return self.retrace_bidirectional_path(
								    __A							,	__A )

							snake_case__				:   Union[str, Any]     =						current_bwd_node
							snake_case__				:   Dict     =						current_fwd_node

							snake_case__				:   List[Any]     =						{
							    self.fwd_bfs: self.fwd_bfs.get_successors(__A ),
							    self.bwd_bfs: self.bwd_bfs.get_successors(__A ),
							}

							for bfs in [self.fwd_bfs, self.bwd_bfs]:
								for node in successors[bfs]:
									bfs.node_queue.append(__A )

						if not self.reached:
							return [self.fwd_bfs.start.pos]
						return None






					def  _lowercase  (      self  :						Any							,	__A  :						Node							,	__A  :						Node ):
						snake_case__				:   List[str]     =						self.fwd_bfs.retrace_path(__A )
						snake_case__				:   Optional[Any]     =						self.bwd_bfs.retrace_path(__A )
						bwd_path.pop()
						bwd_path.reverse()
						snake_case__				:   List[Any]     =						fwd_path + bwd_path
						return path


if __name__ == "__main__":
	# all coordinates are given in format [y,x]
	import doctest

	doctest.testmod()
	__lowerCamelCase      :    str   		=   (0, 0)
	__lowerCamelCase      :    List[str]   		=   (len(grid) - 1, len(grid[0]) - 1)
	for elem in grid:
		print(elem)

	__lowerCamelCase      :    Any   		=   time.time()
	__lowerCamelCase      :    Optional[Any]   		=   BreadthFirstSearch(init, goal)
	__lowerCamelCase      :    str   		=   bfs.search()
	__lowerCamelCase      :    Optional[Any]   		=   time.time() - start_bfs_time

	print("""Unidirectional BFS computation time : """, bfs_time)

	__lowerCamelCase      :    Optional[Any]   		=   time.time()
	__lowerCamelCase      :    Optional[int]   		=   BidirectionalBreadthFirstSearch(init, goal)
	__lowerCamelCase      :    str   		=   bd_bfs.search()
	__lowerCamelCase      :    Optional[Any]   		=   time.time() - start_bd_bfs_time

	print("""Bidirectional BFS computation time : """, bd_bfs_time)



