Closest Nodes Queries in a Binary Search Tree

Inorder traversal of a BST produces sorted keys. Materialize that list once, then for each query q use lower_bound, the first value not less than q. If that value equals q, it is both floor and ceiling. Otherwise the predecessor immediately before lower_bound is the floor when it exists, and lower_bound itself is the ceiling when it exists; use -1 for a missing side. This is often simpler and less error-prone than walking the tree separately for each query. State the memory trade-off: traversal costs O(n), each query costs O(log n), and storage is O(n). If memory matters or queries are few, a direct root-to-leaf walk can maintain best floor and ceiling in O(height) per query.