from typing import Optional, Generator, Tuple


class BinarySearchNode:
    def __init__(self, label: int,
                 parent: Optional['BinarySearchNode']=None,
                 left_child: Optional['BinarySearchNode']=None,
                 right_child: Optional['BinarySearchNode']=None) -> None:
        self.label = label
        self.parent = parent
        self.left_child = left_child
        self.right_child = right_child
        self.update_parent()

    def __str__(self) -> str:
        return f'{self.__class__.__name__} {self.label}'

    def update_parent(self) -> None:
        if not self.parent:
            return # root node
        parent_label = self.parent.label
        if parent_label < self.label:
            self.parent.right_child = self
        else:
            self.parent.left_child = self


class BinarySearchTree:
    def __init__(self) -> None:
        self.root = None

    def min(self, start_node: Optional[BinarySearchNode] = None) -> Optional[BinarySearchNode]:
        if not start_node:
            start_node = self.root
        if not start_node:
            return None # empty tree

        last_taversed_node = start_node
        while last_taversed_node.left_child:
            last_taversed_node = last_taversed_node.left_child

        return last_taversed_node

    def max(self, start_node: Optional[BinarySearchNode] = None) -> Optional[BinarySearchNode]:
        if not start_node:
            start_node = self.root
        if not start_node:
            return None # empty tree

        last_taversed_node = start_node
        while last_taversed_node.right_child:
            last_taversed_node = last_taversed_node.right_child

        return last_taversed_node

    def prev(self, node: BinarySearchNode) -> Optional[BinarySearchNode]:
        # if node has left subtree, return max from that subtree
        if node.left_child:
            return self.max(start_node=node.left_child)

        # traverse parents until a parent with a lower value is reached
        next_node = node
        while next_node:
            if next_node.label < node.label:
                return next_node
            next_node = next_node.parent

        return None # input node is the min

    def next(self, node: BinarySearchNode) -> Optional[BinarySearchNode]:
        # if node has right subtree, return min from that subtree
        if node.right_child:
            return self.min(start_node=node.right_child)

        # traverse parents until a parent with a higher value is reached
        next_node = node
        while next_node:
            if next_node.label > node.label:
                return next_node
            next_node = next_node.parent

        return None # input node is the max

    def traverse_in_order(self) -> Generator[BinarySearchNode, None, None]:
        min_node = self.min()
        if min_node:
            next_node = min_node
            while next_node:
                yield next_node
                next_node = self.next(next_node)

    def search(self, start_node: BinarySearchNode, target_key: int) -> Tuple[bool, BinarySearchNode]:
        """
        returns a tuple representing (was_found, last_traversed_node)
        """
        start_key = start_node.label
        if start_key < target_key:
            child_node = start_node.right_child
        else:
            child_node = start_node.left_child

        if child_node == None:
            return (False, start_node)

        child_key = child_node.label
        if child_key == target_key:
            return (True, start_node)

        return self.search(child_node, target_key)

    def insert(self, key: int) -> BinarySearchNode:
        if not self.root:
            self.root = BinarySearchNode(key, parent=None)
            return self.root

        res = self.search(self.root, key)
        found, last_traversed_node = res

        if found:
            return None # duplicate keys not supported

        return BinarySearchNode(key, parent=last_traversed_node)

@@ -145,33 +145,35 @@
 narySearchNode'%5D
-=
+ = 
 None,%0A          
@@ -215,25 +215,27 @@
 SearchNode'%5D
-=
+ = 
 None,%0A      
@@ -286,17 +286,19 @@
 chNode'%5D
-=
+ = 
 None) -%3E
@@ -638,16 +638,17 @@
  return 
+ 
 # root n
@@ -1114,32 +1114,33 @@
     return None 
+ 
 # empty tree%0A%0A  
@@ -1530,16 +1530,17 @@
 rn None 
+ 
 # empty 
@@ -2209,32 +2209,33 @@
     return None 
+ 
 # input node is 
@@ -2733,16 +2733,17 @@
 rn None 
+ 
 # input 
@@ -3430,18 +3430,18 @@
 ld_node 
-==
+is
  None:%0A 
@@ -3458,17 +3458,16 @@
  return 
-(
 False, s
@@ -3467,33 +3467,32 @@
 alse, start_node
-)
 %0A%0A        child_
@@ -3569,17 +3569,16 @@
  return 
-(
 True, st
@@ -3581,25 +3581,24 @@
 , start_node
-)
 %0A%0A        re
@@ -3908,16 +3908,16 @@
  found:%0A
-
         
@@ -3932,16 +3932,17 @@
 rn None 
+ 
 # duplic

update formatting for linting