in a binary search tree bst the floor of key k is the maximum value that is smaller than or equal to k the ceiling of key k is the minimum value that is greater than or equal to k reference https bit ly46ub0a2 arunkumar date 14th october 2023 find the floor and ceiling values for a given key in a binary search tree bst args root the root of the binary search tree key the key for which to find the floor and ceiling returns a tuple containing the floor and ceiling values respectively examples root node10 root left node5 root right node20 root left left node3 root left right node7 root right left node15 root right right node25 tupleroot 3 5 7 10 15 20 25 floorceilingroot 8 7 10 floorceilingroot 14 10 15 floorceilingroot 1 none 3 floorceilingroot 30 25 none find the floor and ceiling values for a given key in a binary search tree bst args root the root of the binary search tree key the key for which to find the floor and ceiling returns a tuple containing the floor and ceiling values respectively examples root node 10 root left node 5 root right node 20 root left left node 3 root left right node 7 root right left node 15 root right right node 25 tuple root 3 5 7 10 15 20 25 floor_ceiling root 8 7 10 floor_ceiling root 14 10 15 floor_ceiling root 1 none 3 floor_ceiling root 30 25 none
from __future__ import annotations

from collections.abc import Iterator
from dataclasses import dataclass


@dataclass
class Node:
    key: int
    left: Node | None = None
    right: Node | None = None

    def __iter__(self) -> Iterator[int]:
        if self.left:
            yield from self.left
        yield self.key
        if self.right:
            yield from self.right

    def __len__(self) -> int:
        return sum(1 for _ in self)


def floor_ceiling(root: Node | None, key: int) -> tuple[int | None, int | None]:
    
    floor_val = None
    ceiling_val = None

    while root:
        if root.key == key:
            floor_val = root.key
            ceiling_val = root.key
            break

        if key < root.key:
            ceiling_val = root.key
            root = root.left
        else:
            floor_val = root.key
            root = root.right

    return floor_val, ceiling_val


if __name__ == "__main__":
    import doctest

    doctest.testmod()