AlgoViz
HomeBinary Search Trees

Floor in a Binary Search Tree

Easy

Largest value not above the key

Problem

Given a BST and a key, return the floor: the largest value in the tree that is <= key.

In simple words

Walk down the BST, updating the floor whenever you move right to a smaller-or-equal value.

The idea

Descend from the root: when a node's value is at most the key, remember it and move right in case a larger valid value exists; otherwise move left. The last remembered value is the floor.

The trick

  • Remember, then go right — going right without recording loses the answer.
  • Return null or a sentinel when every value exceeds the key.

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
9
0
1
2
3
4
5

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

1/2
Optimal
timeO(h)spaceO(1)
1floor=null; cur=root2while cur:3  if cur.val<=key: floor=cur.val; cur=cur.right4  else: cur=cur.left5return floor

Input

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

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(opens in a new tab)

Finished the walkthrough? Add it to your streak.