AlgoViz
HomeBinary Search Trees

Floor and Ceil in a BST

Easy

Record the candidate as you descend

Problem

Given a BST and a key, return the floor (largest value <= key) and ceil (smallest value >= key).

In simple words

Walk down the BST: going right updates the floor, going left updates the ceil.

The idea

Walk down comparing with the key: whenever a node is at most the key it becomes the best floor so far and you go right to look for something closer; the ceil is the mirror. One descent finds both, in O(height).

The trick

  • Update the candidate before moving, then continue in the direction that could improve it.
  • An exact match is both the floor and the ceil.

This one walks through the worked example rather than tracing the algorithm frame by frame — a full walkthrough is still to be drawn. The code and the idea below are the real solution.

2
5
8
10
12
6
0
1
2
3
4
5

Step 1 of 2. Here's the example — BST {2,5,8,10,12}, key=6 Values: 2, 5, 8, 10, 12, 6.

1/2
Optimal
timeO(h)spaceO(1)
1floor=ceil=null; cur=root2while cur:3  if cur.val==key: return key,key4  if cur.val<key: floor=cur.val; cur=cur.right5  else: ceil=cur.val; cur=cur.left

Input

array
[2, 5, 8, 10, 12, 6]

Output

answer
—

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Examples

Example 1

Input:
bst = [8,4,12,2,6,10,14], x = 5
Output:
[4, 6]
Explanation:
Floor 4, ceil 6.

Example 2

Input:
bst = [8,4,12], x = 8
Output:
[8, 8]
Explanation:
8 is both floor and ceil.

Example 3

Input:
bst = [8,4,12], x = 20
Output:
[12, -1]
Explanation:
No ceil above 20 → -1.

Practice this problem:GeeksforGeeks · floor(opens in a new tab)GeeksforGeeks · ceil(opens in a new tab)

Finished the walkthrough? Add it to your streak.