Introduction

The Floor in BST problem is one of the most important Binary Search Tree interview questions for beginners.

This problem helps you understand:

1. BST traversal
2. Recursive searching
3. Tree optimization
4. Decision making using BST properties
5. Efficient searching techniques

The main idea is to efficiently find the:

Greatest value smaller than or equal to k.

Problem Link

🔗 GeeksforGeeks – Floor in BST

Problem Statement

Given the root of a Binary Search Tree and an integer:

find the:

The floor of a number is:

The greatest value in the BST that is less than or equal to k.

If no such value exists:

Example 1

Input

Output

Explanation

The largest value smaller than or equal to:

is:

Example 2

Input

Output

Key Observation

Binary Search Tree follows:

This ordering allows optimized searching.

Intuition

Suppose:

and current node is:

Since:

this node can potentially be the floor.

But maybe there exists a larger valid floor in the right subtree.

So:

1. Store current node as possible answer
2. Move right

BST Logic

Case 1

If:

then exact floor exists.

Return immediately.

Case 2

If:

current node cannot be floor.

Move left.

Case 3

If:

current node becomes possible floor.

Move right to search for larger valid answer.

Brute Force Approach

Idea

Traverse the entire BST:

1. Store all values smaller than or equal to k
2. Return maximum among them

Brute Force Complexity

Time Complexity

Space Complexity

If storing nodes.

Optimized Recursive BST Approach

Using BST properties:

1. Ignore unnecessary branches
2. Search efficiently
3. Reduce traversal operations

Java Solution

How the Solution Works

Whenever:

the node becomes a possible floor candidate.

But there may exist a larger valid floor in the right subtree.

So:

1. Save current node
2. Move right

Dry Run

Input

Step 1

Current node:

Since:

Possible floor:

Move right.

Step 2

Current node:

Since:

Move left.

Step 3

Current node:

Since:

Update floor:

Move right.

Step 4

Right child is null.

Return:

Final Answer

Optimized Iterative Approach

The same problem can also be solved iteratively.

Iterative Java Solution

Why Iterative Approach is Better

Advantages:

1. Avoids recursion stack
2. More memory efficient
3. Better for skewed trees
4. Preferred in some interviews

Time Complexity Analysis

Best Case

Balanced BST.

Worst Case

Skewed BST.

Space Complexity

Recursive

where H is tree height.

Iterative

extra space.

Interview Explanation

In interviews explain:

Whenever we encounter a node smaller than k, it becomes a possible floor candidate. Then we move right to search for a larger valid floor.

This demonstrates:

1. BST property understanding
2. Search optimization
3. Recursive reasoning
4. Efficient traversal

Common Mistakes

1. Traversing Entire Tree

BST ordering already helps reduce search space.

2. Forgetting to Update Floor

Always update:

before moving right.

3. Returning First Smaller Value

Need the:

not any smaller value.

4. Ignoring Exact Match

If:

return immediately.

FAQs

Q1. What is floor in BST?

Largest value smaller than or equal to k.

Q2. Why move right after finding smaller value?

To search for a larger valid floor.

Q3. Can this be solved iteratively?

Yes.

Iterative solution is highly optimized.

Q4. What if floor does not exist?

Return:

Related BST Problems

Practice these next:

1. Ceil in BST
2. Search in BST
3. Insert into BST
4. Validate BST
5. Lowest Common Ancestor in BST

Conclusion

Floor in BST is an excellent problem for understanding:

1. BST traversal
2. Recursive searching
3. Search space optimization
4. Interview tree concepts

The key insight is:

Whenever a node is smaller than k, it becomes a possible floor candidate, but a larger valid floor may still exist in the right subtree.

Mastering this logic makes many BST interview problems much easier.