Floor and ceiling queries in a Python BST

Why it matters

Many questions are not "is this value here?" but "what is the nearest value?"

A bus timetable lists departures at 09:10, 09:40 and 10:05. You arrive at 09:52. You want the last departure at or before 09:52, which is 09:40. A shop with a sorted price list may want the most expensive item that still fits a budget. A memory allocator may want the smallest free block that is large enough. Each of these is a neighbour query: given a value, find the closest stored value on one side of it.

The BST basics lesson showed how to search for an exact value. This lesson uses the same tree and the same walk from the root to answer neighbour questions. The next lesson in the module counts how many values are smaller than a key, which needs the same walk with one extra number stored in each node.

By the end of this lesson you will be able to find the floor and the ceiling of a key in a Python BST, explain why only one path is walked, and avoid the bugs that most beginners write the first time.

Start with the problem

Suppose the values are in a sorted list: 20, 30, 40, 50, 60, 70, 80. You want the floor of 65, which is the largest value less than or equal to 65.

You can scan the list from the left. Keep the last value that is still at or below 65. The scan stops when it reaches 70, because 70 is above 65. The answer is 60.

The scan works, but it looks at up to every item. With a million values it may look at a million items. A BST should do better: each step should throw away one whole side of the tree, as the search in the BST basics lesson did.

Two definitions

The floor of a key x is the largest value in the tree that is less than or equal to x.

The ceiling of a key x is the smallest value in the tree that is greater than or equal to x.

If no such value exists, the answer is "none". For example, the floor of 10 in a tree that holds only values from 20 up has no answer.

In Python, the missing answer is the value None. None means "no object here", and it is different from the number zero. A caller can test for it with is None, so it cannot be mistaken for a real answer. Python does not have a separate wrapper type for this, as Java does with Optional.

The tree we will use

Insert these values in this order into an empty BST: 50, 30, 70, 20, 40, 60, 80. The first value becomes the root. Each later value walks down from the root, going left when it is smaller and right when it is larger, until it finds an empty spot.

        50
       /  \
     30    70
    /  \   /  \
  20   40 60   80

Every node obeys the BST rule: the left side holds smaller values and the right side holds larger values.

Here is the insert code. Duplicates are ignored, so the tree never holds the same value twice.

def insert(root, key):
    if root is None:
        return Node(key)
    if key < root.key:
        root.left = insert(root.left, key)
    elif key > root.key:
        root.right = insert(root.right, key)
    return root

The idea behind the walk

Start at the root. At each node, compare the node's key with the target x. There are three cases.

1. The node's key equals x. The floor and the ceiling are both x. Stop.
2. The node's key is smaller than x. This node is a candidate for the floor, because it is at or below x. Save it. A larger candidate that is still at or below x may exist on the right, so go right.
3. The node's key is larger than x. This node is a candidate for the ceiling, because it is at or above x. Save it. A smaller candidate that is still at or above x may exist on the left, so go left.

When a walk falls off the tree, the saved candidate is the answer. If nothing was saved, the answer is "none".

This works because of case 2 for the floor. The node's key is smaller than x, so the node is a candidate. Its left side holds values smaller than the node, so each of them is worse than the node. You do not need to look there. Only the right side can hold a better floor. The same logic works for case 3 and the ceiling, mirrored.

Each step goes one level down, so the walk takes at most as many steps as the tree has levels. Computer scientists write this cost as O(height). "O(height)" means the number of steps grows with the height of the tree, not with the number of values. The height is the number of nodes on the longest path from the root down to a leaf.

Worked example 1: floor and ceiling of 65

Use the tree above. Here is the floor walk for 65. The column "best" shows the saved candidate after each step.

The ceiling walk for 65 is the mirror image.

The floor is 60 and the ceiling is 70. The walk visited three nodes and then stopped at an empty spot. Nodes 30, 40, 20, 80 were never looked at, because the comparisons ruled out their whole side.

Worked example 2: a value that sits between two stored values

Now find the floor and ceiling of 35. The value 35 is not in the tree.

Floor of 35:

• At 50: 50 is larger than 35, so go left. Nothing saved.
• At 30: 30 is smaller than 35, so save 30 and go right.
• At 40: 40 is larger than 35, so go left.
• At an empty left child: stop. The saved value is 30.

Ceiling of 35:

• At 50: 50 is larger than 35, so save 50 and go left.
• At 30: 30 is smaller than 35, so go right.
• At 40: 40 is larger than 35, so save 40 and go left.
• At an empty left child: stop. The saved value is 40.

The floor is 30 and the ceiling is 40. Notice that the walk went down to a leaf and stopped there. A walk for an absent key always ends at an empty child.

Worked example 3: values outside the range

Some keys are below the smallest value or above the largest one.

The floor of 10 walks left at 50, left at 30, and left at 20. Each comparison says the node is larger than 10, so nothing is ever saved. The walk falls off the tree and the answer is None.

The ceiling of 90 walks right at 50, right at 70, and right at 80. Each node is smaller than 90, so nothing is saved. The answer is again None.

Both cases are handled by the same code. The best variable starts as None, and that is what gets returned when nothing was saved.

Worked example 4: the key is in the tree

If the key is already stored, the walk stops at that node. The floor of 50 is 50, and the ceiling of 50 is 50. The first comparison at the root returns the root's key straight away, so the walk takes one step.

This is also why the code checks for equality before it checks the two directions. Without the equality check, a walk for 50 would not stop at the root. You will see that mistake in the common mistakes section.

Worked example 5: the full program

The program below builds the tree, prints floor and ceiling for six keys, and then checks 1000 random queries against a simple reference. The reference keeps the stored keys in a sorted list and uses bisect, which is a standard module that finds positions in a sorted list. It gives trusted answers, so the walk can be checked against it.

Save the file and run it with python3. The real output is:

target=65 floor=60 ceiling=70
target=35 floor=30 ceiling=40
target=10 floor=none ceiling=20
target=90 floor=80 ceiling=none
target=50 floor=50 ceiling=50
target=20 floor=20 ceiling=20
random queries=1000 mismatches=0

The six printed lines match the worked examples above. The last line says that all 1000 random queries gave the same answer as the sorted-list reference.

Reading the Python code

• The show function turns the answer into text. If the answer is a number, it prints the number. If the answer is None, it prints none.
• The while cur is not None loop is the walk. Each pass moves cur down one level, so the loop runs at most once per level of the tree.
• Node is a small class with one key and two links. It is the same idea as the node in the first lesson.
• random.Random(42) makes a random generator with a fixed seed, so the same numbers appear on every run.

Why the height matters

The number of steps in a walk equals the number of levels the walk passes through, so the cost depends on the height.

In a tree with about the same number of values on each side of every node, the height grows like the number of times you can halve the values. For a million values the height is about 20, so a query takes about 20 steps.

A tree can also become a line. Insert 1, 2, 3, 4, 5, 6, 7 in that order and each new value goes right of the one before it. The tree is then a chain of seven nodes with height 7. The floor of 7 walks through all seven nodes. The lesson "Why sorted input makes a Python BST a chain" explains how this happens and how to avoid it.

So the cost is O(height). For a balanced tree that is O(log n) steps, where n is the number of values. For a chain it is O(n) steps, the same as scanning a list.

Common mistakes

Returning the last node you visited

A beginner often returns the node where the walk stopped, instead of the saved candidate.

For floor(35) on the tree above, the walk visits 50, 30 and 40, then stops. The last node visited is 40, which is larger than 35, so it cannot be the floor. The correct answer is 30, the saved candidate. Always return best, not cur.

Going the wrong way when the node is larger

For the floor code, the rule is: when the node is larger than the target, go left. A beginner may write it the other way round and go right.

Trace floor(35) with that mistake. At 50 the walk goes right to 70. At 70 it goes right to 80. At 80 it goes right and falls off the tree. Nothing was saved, so the result is None. The real floor is 30, which the walk never reached.

Forgetting the equal case

If the code checks only cur.key < target for the floor, a key that is in the tree is missed. The floor of 50 would go left at the root because 50 is not smaller than 50. The walk would save 30, then 40, and return 40. The correct floor is 50.

The fix is the equality check at the top of the loop, which the code above has.

Using a missing answer as a number

floor returns None when no value is at or below the key. Adding one to that result stops the program. Here is a small program that does it, using the same tree as above. It assumes the code from the run block is saved as floor_ceiling.py in the same folder.

from floor_ceiling import insert, floor
 
root = None
for key in [50, 30, 70, 20, 40, 60, 80]:
    root = insert(root, key)
print(floor(root, 10) + 1)

Importing the module also runs its run block, so the output starts with the seven lines that block prints. The real output ends with this message:

TypeError: unsupported operand type(s) for +: 'NoneType' and 'int'

The message means the value was None, which cannot be added to a number. Check with is None first, or use a default value, and only then use the answer as a number.

Assuming a sorted insert order is harmless

Inserting sorted values builds a chain, as described above. The code is still correct, but each query now takes O(n) steps instead of O(log n). Check the height of the tree when a query looks slow.

Practice

Exercise 1. Use the tree 50, 30, 70, 20, 40, 60, 80. Find the floor and the ceiling of 45.

Show the answer

The floor is 40 and the ceiling is 50. The walk for the floor goes left at 50, saves 30 and goes right, then saves 40 and goes right to an empty child. The walk for the ceiling saves 50 at the root, goes left, goes right at 30, then reaches 40, which is smaller than 45, so it goes right to an empty child and returns 50.

Exercise 2. Insert 10, then 20, then 5 into an empty BST. Find the floor and the ceiling of 7.

Show the answer

The tree has 10 at the root, 5 on the left and 20 on the right. The floor of 7 is 5: at 10 the walk goes left, and 5 is smaller than 7, so 5 is saved and the walk goes right to an empty child. The ceiling of 7 is 10: at 10 the node is larger, so 10 is saved and the walk goes left to 5, which is smaller, so it goes right to an empty child and returns 10.

Exercise 3. Insert 1, 2, 3, 4, 5, 6, 7 in that order. How many nodes does the floor walk of 7 visit, and why?

Show the answer

The walk visits 7 nodes: 1, 2, 3, 4, 5, 6 and 7. Each insert went to the right of the value before it, so the tree is a chain. Every node has only a right child, so the walk cannot skip any node. The height is 7, so the cost is 7 steps, the same as scanning the list.

Exercise 4. A teammate writes the floor walk this way: "When the node is smaller than the target, return that node, because it is the floor." Give a query on the tree 50, 30, 70, 20, 40, 60, 80 where this gives a wrong answer.

Show the answer

Take the floor of 65. At the root, 50 is smaller than 65, so the rule returns 50. The real floor is 60, because 60 is also at or below 65 and it is larger than 50. The rule stops too early. The correct walk saves 50 and keeps going to the right.

Summary

• The floor of x is the largest stored value at or below x. The ceiling is the smallest stored value at or above x.
• A walk from the root saves a candidate each time it goes past a node on the correct side, then returns the last candidate it saved.
• Each step discards one whole side of the tree, so the walk takes O(height) steps.
• Check for an exact match first, so that a stored key is returned as its own floor and ceiling.
• Return None when no candidate exists, and test with is None before using the value.