+ def _find_lowest_node_less_than_or_equal_to(
+ self, target: Comparable, node: Optional[Node]
+ ) -> Optional[Node]:
+ """Find helper that returns the lowest node that is less
+ than or equal to the target value. Returns None if target is
+ lower than the lowest node in the tree.
+
+ >>> t = BinarySearchTree()
+ >>> t.insert(50)
+ >>> t.insert(75)
+ >>> t.insert(25)
+ >>> t.insert(66)
+ >>> t.insert(22)
+ >>> t.insert(13)
+ >>> t.insert(85)
+ >>> t
+ 50
+ ├──25
+ │ └──22
+ │ └──13
+ └──75
+ ├──66
+ └──85
+
+ >>> t._find_lowest_node_less_than_or_equal_to(48, t.root).value
+ 25
+ >>> t._find_lowest_node_less_than_or_equal_to(55, t.root).value
+ 50
+ >>> t._find_lowest_node_less_than_or_equal_to(100, t.root).value
+ 85
+ >>> t._find_lowest_node_less_than_or_equal_to(24, t.root).value
+ 22
+ >>> t._find_lowest_node_less_than_or_equal_to(20, t.root).value
+ 13
+ >>> t._find_lowest_node_less_than_or_equal_to(72, t.root).value
+ 66
+ >>> t._find_lowest_node_less_than_or_equal_to(78, t.root).value
+ 75
+ >>> t._find_lowest_node_less_than_or_equal_to(12, t.root) is None
+ True
+
+ """
+
+ if not node:
+ return None
+
+ if target == node.value:
+ return node
+
+ elif target > node.value:
+ if below := self._find_lowest_node_less_than_or_equal_to(
+ target, node.right
+ ):
+ return below
+ else:
+ return node
+
+ else:
+ return self._find_lowest_node_less_than_or_equal_to(target, node.left)
+
+ def _find_lowest_node_greater_than_or_equal_to(
+ self, target: Comparable, node: Optional[Node]
+ ) -> Optional[Node]:
+ """Find helper that returns the lowest node that is greater
+ than or equal to the target value. Returns None if target is
+ higher than the greatest node in the tree.
+
+ >>> t = BinarySearchTree()
+ >>> t.insert(50)
+ >>> t.insert(75)
+ >>> t.insert(25)
+ >>> t.insert(66)
+ >>> t.insert(22)
+ >>> t.insert(13)
+ >>> t.insert(85)
+ >>> t
+ 50
+ ├──25
+ │ └──22
+ │ └──13
+ └──75
+ ├──66
+ └──85
+
+ >>> t._find_lowest_node_greater_than_or_equal_to(48, t.root).value
+ 50
+ >>> t._find_lowest_node_greater_than_or_equal_to(55, t.root).value
+ 66
+ >>> t._find_lowest_node_greater_than_or_equal_to(1, t.root).value
+ 13
+ >>> t._find_lowest_node_greater_than_or_equal_to(24, t.root).value
+ 25
+ >>> t._find_lowest_node_greater_than_or_equal_to(20, t.root).value
+ 22
+ >>> t._find_lowest_node_greater_than_or_equal_to(72, t.root).value
+ 75
+ >>> t._find_lowest_node_greater_than_or_equal_to(78, t.root).value
+ 85
+ >>> t._find_lowest_node_greater_than_or_equal_to(95, t.root) is None
+ True
+
+ """
+
+ if not node:
+ return None
+
+ if target == node.value:
+ return node
+
+ elif target > node.value:
+ return self._find_lowest_node_greater_than_or_equal_to(target, node.right)
+
+ # If target < this node's value, either this node is the
+ # answer or the answer is in this node's left subtree.
+ else:
+ if below := self._find_lowest_node_greater_than_or_equal_to(
+ target, node.left
+ ):
+ return below
+ else:
+ return node
+