Floor and ceiling queries in a BST

Why this matters

A search asks one question: is this exact key in the tree? Many real questions are different. Suppose a shop keeps its prices in a binary search tree (BST), a tree where every key in a node's left subtree is smaller and every key in its right subtree is larger. The prices are 5, 10, 15, 20, 25, 30 and 35 dollars. A customer has 12 dollars and asks which item is the most expensive one they can afford. The answer is 10, even though 12 is not a price in the tree. A second customer asks for the cheapest item that costs at least 12. The answer is 15.

The first question is a floor query. The second is a ceiling query. Both return a key near the target, not necessarily the target itself. This lesson shows how to answer both in one walk down the tree. It assumes you already know how to insert a key and search for it, which the first lesson in this module covers. The other lessons in this module use the same walk for different questions, such as range sums and the lowest common ancestor.

The idea

A key is the number stored in a node. Two terms carry the rest of this lesson:

• The floor of a target is the largest key in the tree that is less than or equal to the target.
• The ceiling of a target is the smallest key in the tree that is greater than or equal to the target.

If no key qualifies, the answer is "none". In C++ we return std::optional<int>. An optional is a box that either holds an int or holds nothing. The empty box is written std::nullopt, and it is how a function says "there is no answer" without using a special number such as -1, which could be a real key.

Start with a small tree. Insert 20, 10, 30, 5, 15, 25 and 35 in that order. The result looks like this:

        20
      /    \
    10      30
   /  \    /  \
  5   15  25  35

Here are the answers for four targets:

When the target is already in the tree, floor and ceiling both return that key. When the target is below every key, the floor is none. When it is above every key, the ceiling is none.

Walking down one path

Look at floor(12) on the tree above. We do not need to check every node. We follow one path from the root and keep a note of the best answer so far.

1. Start at the root, 20. It is not equal to 12. It is bigger than 12, so it cannot be the floor. Every key in its right subtree is bigger still, so the floor must be on the left. Go left.
2. We are at 10. It is not equal to 12. It is smaller than 12, so it fits. Write down 10 as the best answer so far. Keys on the right of 10 might fit too and might be closer to 12, so look right.
3. We are at 15. It is bigger than 12, so it does not fit. Go left.
4. The left child of 15 is empty. Stop. The best answer is 10.

Three rules come out of that trace. Use them for every node on the path:

• If the node equals the target, return the node. It is the answer for both floor and ceiling.
• If the node is smaller than the target, it is a floor candidate. Remember it, then go right to look for a bigger candidate.
• If the node is bigger than the target, it cannot be a floor. Go left.

Ceiling uses the same walk with the directions swapped. Trace ceiling(12). The root 20 is bigger than 12, so it is a ceiling candidate. Remember 20 and go left. Node 10 is smaller than 12, so it is not a ceiling. Go right to 15. It is bigger than 12, so it is a candidate and it is closer than 20. Remember 15 and go left. The left child is empty. The answer is 15.

Why keep going after the first candidate? Because a candidate can be correct and still not be the closest one. In the ceiling trace, 20 was a valid answer but 15 was better. The walk keeps replacing the candidate with a closer one until it runs out of path.

Floor and ceiling in C++

The insert function below is the one you saw in the search lesson, with one change: a duplicate key is ignored, so every key appears at most once. The two query functions follow the three rules above.

#include <memory>
#include <optional>
 
struct Node {
    int key;
    std::unique_ptr<Node> left;
    std::unique_ptr<Node> right;
    explicit Node(int k) : key(k) {}
};
 
// Insert a key. Duplicates are ignored.
std::unique_ptr<Node> insert(std::unique_ptr<Node> node, int key) {
    if (!node) return std::make_unique<Node>(key);
    if (key < node->key) {
        node->left = insert(std::move(node->left), key);
    } else if (key > node->key) {
        node->right = insert(std::move(node->right), key);
    }
    return node;
}
 
// Largest key that is <= target, or std::nullopt if every key is larger.
std::optional<int> floor_key(const Node* node, int target) {
    std::optional<int> best;
    while (node) {
        if (node->key == target) return node->key;
        if (node->key < target) {
            best = node->key;             // fits, but a bigger fit may exist on the right
            node = node->right.get();
        } else {
            node = node->left.get();      // too big, so every answer is on the left
        }
    }
    return best;
}
 
// Smallest key that is >= target, or std::nullopt if every key is smaller.
std::optional<int> ceiling_key(const Node* node, int target) {
    std::optional<int> best;
    while (node) {
        if (node->key == target) return node->key;
        if (node->key > target) {
            best = node->key;             // fits, but a smaller fit may exist on the left
            node = node->left.get();
        } else {
            node = node->right.get();     // too small, so every answer is on the right
        }
    }
    return best;
}

The functions take a const Node*, a plain pointer that is allowed to be null. They only read the tree, so the const says so. The while (node) loop stops at the first empty spot, which means the functions never follow a null pointer.

Here is a main function that runs the queries from the tree above and prints the results:

#include <iostream>
#include <string>
 
std::string show(std::optional<int> v) {
    return v ? std::to_string(*v) : std::string("none");
}
 
int main() {
    std::unique_ptr<Node> root;
    for (int k : {20, 10, 30, 5, 15, 25, 35}) {
        root = insert(std::move(root), k);
    }
 
    for (int q : {12, 4, 25, 40, 15}) {
        std::cout << "query " << q
                  << ": floor=" << show(floor_key(root.get(), q))
                  << " ceiling=" << show(ceiling_key(root.get(), q)) << '\n';
    }
}

Compiled with g++ -std=c++20 -Wall, the program prints:

query 12: floor=10 ceiling=15
query 4: floor=none ceiling=5
query 25: floor=25 ceiling=25
query 40: floor=35 ceiling=none
query 15: floor=15 ceiling=15

Every line matches the table above. The show helper turns the optional into text. It uses the ternary operator ?:, which reads as "if there is a value, print it, otherwise print none".

A second example: a tree that is not built in order

The first tree was built from a list that started near the middle, so it has a nice shape. The walk works the same way on any tree. Insert 50, 40, 60, 45, 55 and 47, in that order. The tree has a longer path on the left side of 50.

          50
        /    \
      40      60
        \    /
         45 55
          \
           47

Find floor(46). Start at 50. It is bigger than 46, so go left. We are at 40. It is smaller than 46, so it is a candidate. Go right. We are at 45. It is smaller than 46, so it is a better candidate. Go right. We are at 47. It is bigger than 46, so go left. The left child of 47 is empty. The answer is 45.

Find ceiling(46). Start at 50. It is bigger than 46, so it is a candidate. Go left. We are at 40. It is smaller than 46, so go right. We are at 45. It is smaller, so go right. We are at 47. It is bigger than 46 and closer than 50, so it replaces the candidate. Go left. The left child is empty. The answer is 47.

Run the same two calls in a program, and you get floor(46)=45 ceiling(46)=47. The two answers sit side by side because the target falls between two keys that are neighbours in sorted order. This is a useful check for your own understanding: floor and ceiling return the same key only when the target is in the tree, and otherwise they return the two keys directly around the target.

A third example: the closest key

Many questions need one answer, not two. What is the price closest to 17 dollars? That is the closer of the floor and the ceiling. The function below calls both queries and compares the distances.

// Closest key to target. Ties go to the smaller key.
std::optional<int> closest_key(const Node* node, int target) {
    auto lo = floor_key(node, target);
    auto hi = ceiling_key(node, target);
    if (!lo) return hi;
    if (!hi) return lo;
    return (target - *lo <= *hi - target) ? lo : hi;
}

If there is no floor, the closest key must be the ceiling, and the other way round. If both exist, compare the distance from the target to each. The distance is never negative, so the subtraction is safe in this order.

With the price tree from the first example (5, 10, 15, 20, 25, 30, 35), the results are:

The tie rule matters when the target is exactly halfway. Take the tree with keys 10 and 20 and target 15. The floor is 10 and the ceiling is 20. Both are 5 away. The code returns 10, the smaller key. Change the comparison to < and the tie goes to the larger key instead. Pick one rule and write it in the function's comment, so the next reader knows what happens.

Why it takes time proportional to the height

Each step of the walk moves one level down the tree. The walk stops at the first empty child, so it never goes deeper than the tree's height. The height is the number of edges on the longest path from the root to a leaf. A tree of one node has height 0.

This gives two cases:

• A balanced tree, where each level is nearly full, has a height close to the base-2 logarithm of the number of keys. A tree with 1023 keys has 10 levels, so a query needs at most about 10 steps.
• A chain, where every node has only one child, has a height equal to the number of keys. A chain of 1000 keys needs up to 1000 steps.

The chain case is what happens when you insert sorted input into a plain BST. The lesson "Why sorted input makes a BST a chain" shows how that happens. The program below builds a chain of 1000 keys by inserting 1 to 1000 in order, then counts the nodes on the path to the key 1000:

std::unique_ptr<Node> chain;
for (int k = 1; k <= 1000; ++k) {
    chain = insert(std::move(chain), k);
}
int visits = 0;
const Node* cur = chain.get();
while (cur) {
    ++visits;
    if (cur->key == 1000) break;
    cur = cur->right.get();
}
std::cout << "nodes on the path to 1000 = " << visits << '\n';

The snippet needs the same includes and insert as above. Its output is:

nodes on the path to 1000 = 1000

Floor and ceiling are O(height) queries, which means the time grows with the height, not with the number of keys. On a balanced tree that is fast. On a chain it is no better than a list scan. The AVL lessons in this module explain how to keep the height small.

Common mistakes

Forgetting the candidate

The most common bug is to walk the path correctly and then return none because the best value was never saved. Here is a version of floor_key that drops the best = node->key; line:

std::optional<int> floor_key_buggy(const Node* node, int target) {
    std::optional<int> best;
    while (node) {
        if (node->key == target) return node->key;
        if (node->key < target) {
            node = node->right.get();
        } else {
            node = node->left.get();
        }
    }
    return best;
}

Print floor_key_buggy(root.get(), 12) on the tree from the first example, with a label in front, and the output is:

floor(12) = none

The correct answer is 10. The walk visited 10, saw that it fit, and then moved on without writing it down. The fix is one line: store the candidate when it fits.

Turning the directions around

It is easy to swap left and right when you write the ceiling version after the floor version. A floor query that goes left when the node is too small and right when it is too big returns the wrong key. Here is a reversed floor:

std::optional<int> floor_reversed(const Node* node, int target) {
    std::optional<int> best;
    while (node) {
        if (node->key == target) return node->key;
        if (node->key < target) {
            node = node->left.get();
        } else {
            best = node->key;
            node = node->right.get();
        }
    }
    return best;
}

On the tree that contains 8, 3, 10, 1, 6, 14, 4, 7 and 13, the result for target 5 is 14. The floor should be 4. The function returned a key that is bigger than the target, which breaks the definition. Check the answer against the definition every time you write one of these functions: a floor must be less than or equal to the target.

Dereferencing an empty child

Accessing node->right->key without checking that node->right exists is a null pointer error. The program does not print a message. It stops with a crash. This is the test program I used:

int crash_on_leaf(const Node* node) {
    return node->right->key;
}

Called on a leaf node, which has no right child, the program exited with code 139. On Linux, that code means the program was stopped by a segmentation fault, the error the operating system raises when code reads memory it does not own. The walk in this lesson avoids this by checking while (node) before reading any field.

Forgetting the include

If a file uses std::optional without including the header, the compiler reports an error. Here is a file with the include left out, compiled with g++ -std=c++20 -Wall:

#include <iostream>
int main() {
    std::optional<int> v = 3;
    std::cout << *v << std::endl;
}

The first lines of the error output are:

missing_include.cpp: In function ‘int main()’:
missing_include.cpp:3:10: error: ‘optional’ is not a member of ‘std’
    3 |     std::optional<int> v = 3;
      |          ^~~~~~~~
missing_include.cpp:2:1: note: ‘std::optional’ is defined in header ‘<optional>’; this is probably fixable by adding ‘#include <optional>’

The compiler names the header you need. Add #include <optional> at the top and the error goes away.

Using a number as the "none" value

Some code returns -1 or 0 when there is no answer. That breaks when the tree holds negative numbers or zero. Return std::nullopt instead, so that "no answer" and "the answer is 0" cannot be confused.

Practice

Exercise 1

Insert 8, 3, 10, 1, 6, 14, 4, 7 and 13 into an empty tree, in that order. Find the floor and ceiling of 5, of 0 and of 15.

Show the answer

Floor(5) is 4 and ceiling(5) is 6. Floor(0) is none, because every key is bigger than 0, and ceiling(0) is 1. Floor(15) is 14 and ceiling(15) is none, because 14 is the largest key. The program in the lesson prints the same values when run on this tree.

Exercise 2

On the tree from Exercise 1, floor(9) returns 8, not 7. Explain why, using the three rules from this lesson.

Show the answer

Start at the root, 8. It is smaller than 9, so it is a floor candidate. Go right, to 10. It is bigger than 9, so go left. The left child of 10 is empty, so the walk stops. Every key on the left of 8 is smaller than 8, so 8 is closer to 9 than any of them, including 7. The walk goes right from 8 and never enters the left side, so 8 is the floor.

Exercise 3

Change closest_key so that a tie goes to the larger key. Explain the one line you changed.

Show the answer

Change the comparison in the last line to a strict less-than, so the floor is chosen only when it is strictly closer:

return (target - *lo < *hi - target) ? lo : hi;

When the two distances are equal, the condition is false, so the function returns hi, the ceiling, which is the larger key. The old code used <=, which chose the floor on a tie.

Exercise 4

Write floor as a recursive function, with the same answers as floor_key.

Show the answer

std::optional<int> floor_recursive(const Node* node, int target) {
    if (!node) return std::nullopt;
    if (node->key == target) return node->key;
    if (node->key > target) return floor_recursive(node->left.get(), target);
    auto from_right = floor_recursive(node->right.get(), target);
    return from_right ? from_right : std::optional<int>(node->key);
}

If the node is too big, the answer is on the left, so the function returns the left result. If the node fits, the function asks the right subtree for a better answer. The right subtree's answer is bigger than the node, so it wins when it exists. Otherwise the node itself is the answer. A test that compared this function with floor_key on 100 random trees of 30 keys each, for every target from -1 to 301, found no differences.

Summary

• A floor is the largest key at or below the target. A ceiling is the smallest key at or above it. Both return std::nullopt when no key qualifies.
• Walk one path from the root. Keep the best fit seen so far, and move left or right depending on whether the node is too big or too small.
• Each step goes one level down, so a query takes time proportional to the tree height.
• On a balanced tree the height is about the base-2 logarithm of the key count. On a chain it equals the key count.
• The two most common bugs are forgetting to save the candidate and swapping the left and right directions.