Adds find_lowest_node_less_than_or_equal_to.

diff --git a/src/pyutils/collectionz/bst.py b/src/pyutils/collectionz/bst.py
index 343ddc0763c39d93c3db7737c935e205e58edf99..cefbf59ba12c4050a0c63d6601ba941e265a8543 100644 (file)
--- a/src/pyutils/collectionz/bst.py
+++ b/src/pyutils/collectionz/bst.py
@@ -119,25 +119,88 @@ class BinarySearchTree(object):
 
         """
         if self.root is not None:
-            return self._find(value, self.root)
+            return self._find_exact(value, self.root)
         return None
 
-    def _find(self, value: ComparableNodeValue, node: Node) -> Optional[Node]:
-        """Find helper"""
-        if value == node.value:
+    def _find_exact(self, target: ComparableNodeValue, node: Node) -> Optional[Node]:
+        """Recursively traverse the tree looking for a node with the
+        target value.  Return that node if it exists, otherwise return
+        None."""
+
+        if target == node.value:
             return node
-        elif value < node.value and node.left is not None:
-            return self._find(value, node.left)
-        elif value > node.value and node.right is not None:
-            return self._find(value, node.right)
+        elif target < node.value and node.left is not None:
+            return self._find_exact(target, node.left)
+        elif target > node.value and node.right is not None:
+            return self._find_exact(target, node.right)
         return None
 
-    def _find_lowest_value_greater_than_or_equal_to(
+    def _find_lowest_node_less_than_or_equal_to(
+        self, target: ComparableNodeValue, 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: ComparableNodeValue, 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
-        greater than the highest node in the tree.
+        higher than the greatest node in the tree.
 
         >>> t = BinarySearchTree()
         >>> t.insert(50)
@@ -156,21 +219,21 @@ class BinarySearchTree(object):
            ├──66
            └──85
 
-        >>> t._find_lowest_value_greater_than_or_equal_to(48, t.root).value
+        >>> t._find_lowest_node_greater_than_or_equal_to(48, t.root).value
         50
-        >>> t._find_lowest_value_greater_than_or_equal_to(55, t.root).value
+        >>> t._find_lowest_node_greater_than_or_equal_to(55, t.root).value
         66
-        >>> t._find_lowest_value_greater_than_or_equal_to(1, t.root).value
+        >>> t._find_lowest_node_greater_than_or_equal_to(1, t.root).value
         13
-        >>> t._find_lowest_value_greater_than_or_equal_to(24, t.root).value
+        >>> t._find_lowest_node_greater_than_or_equal_to(24, t.root).value
         25
-        >>> t._find_lowest_value_greater_than_or_equal_to(20, t.root).value
+        >>> t._find_lowest_node_greater_than_or_equal_to(20, t.root).value
         22
-        >>> t._find_lowest_value_greater_than_or_equal_to(72, t.root).value
+        >>> t._find_lowest_node_greater_than_or_equal_to(72, t.root).value
         75
-        >>> t._find_lowest_value_greater_than_or_equal_to(78, t.root).value
+        >>> t._find_lowest_node_greater_than_or_equal_to(78, t.root).value
         85
-        >>> t._find_lowest_value_greater_than_or_equal_to(95, t.root) is None
+        >>> t._find_lowest_node_greater_than_or_equal_to(95, t.root) is None
         True
 
         """
@@ -182,12 +245,12 @@ class BinarySearchTree(object):
             return node
 
         elif target > node.value:
-            return self._find_lowest_value_greater_than_or_equal_to(target, node.right)
+            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_value_greater_than_or_equal_to(
+            if below := self._find_lowest_node_greater_than_or_equal_to(
                 target, node.left
             ):
                 return below
@@ -714,7 +777,7 @@ class BinarySearchTree(object):
         50
         66
         """
-        node: Optional[Node] = self._find_lowest_value_greater_than_or_equal_to(
+        node: Optional[Node] = self._find_lowest_node_greater_than_or_equal_to(
             lower, self.root
         )
         while node: