Log inSign up
easyGeeksforGeeksNot Started

Floor in BST

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

BST
Solve on GeeksforGeeks
Lesson

Problem Statement

### Problem Statement

Given a Binary Search Tree (BST) and an integer key X, find the floor of X in the BST.

The floor of X is defined as the greatest value in the BST that is smaller than or equal to X (val <= X). If no such value exists (i.e., all elements in the BST are greater than X), return -1.

---

### Examples

Example 1: ```text 8 / \ 4 12 / \ 2 6

Input: root = [8, 4, 12, 2, 6], X = 5 Output: 4 Explanation: The nodes smaller than or equal to 5 are 2 and 4. The greatest among them is 4. ```

Example 2: ```text 8 / \ 4 12 / \ 2 6

Input: root = [8, 4, 12, 2, 6], X = 1 Output: -1 Explanation: All values in the BST are greater than 1, so no floor exists. ```

---

### Constraints - The number of nodes in the tree is in the range [1, 10^5]. - 1 <= Node.val <= 10^6 - 1 <= X <= 10^6

Constraints:

  • The number of nodes in the tree is in the range [1, 105].
  • 1 <= Node.val <= 106
  • 1 <= X <= 106

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Understand the floor definition in search trees (greatest value <= X).
  • Learn how to guide binary search while updating the best candidate seen so far.
  • Implement the search with O(H) time and O(1) auxiliary space.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Finding closest smaller or equal element in a sorted tree structure
  • Target comparison where one direction preserves candidate validity
  • Binary search decision tree matching

Algorithmic Decision Tree:

  • If curr.val == X -> return X immediately (exact match is optimal floor).
  • If curr.val < X -> record candidate = curr.val and move right to search for larger candidates.
  • If curr.val > X -> candidate cannot be here; move left.

Connected Patterns:

Ceil in BSTSearch in a Binary Search TreeInorder Predecessor in BST

1. Inorder Traversal Array Scan

Intuition

Since in-order traversal of a BST gives sorted order, we can collect all elements into an array and find the last element <= X.

Algorithm

  1. Collect all tree values into a list using in-order traversal.
  2. Initialize floor = -1.
  3. Iterate through sorted values: if val <= X, update floor = val. If val > X, break.
  4. Return floor.

Inorder Array Scan for X = 5

2 of 2 questions left today
Step 1 / 5
Trace timeline20% explored
Current operationSTEP 1 OF 5
Inorder traversal produces sorted list: [2, 4, 6, 8, 12]
Visual state
Values and pointers at this exact step
array
S
[2, 4, 6, 8, 12]
0
Check / comparison
Collected
Decision / next transition
List ready
Why this step matters

Inorder traversal produces sorted list: [2, 4, 6, 8, 12].

Step 1 / 5
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4struct TreeNode {
5 int val;
6 TreeNode *left;
7 TreeNode *right;
8 TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
9};
10
11class Solution {
12 void inorder(TreeNode* root, std::vector<int>& arr) {
13 if (!root) return;
14 inorder(root->left, arr);
15 arr.push_back(root->val);
16 inorder(root->right, arr);
17 }
18public:
19 int floorInBST(TreeNode* root, int X) {
20 std::vector<int> arr;
21 inorder(root, arr);
22 int floorVal = -1;
23 for (int v : arr) {
24 if (v <= X) floorVal = v;
25 else break;
26 }
27 return floorVal;
28 }
29};
30
31int main() {
32 TreeNode* root = new TreeNode(8);
33 root->left = new TreeNode(4);
34 root->right = new TreeNode(12);
35 root->left->left = new TreeNode(2);
36 root->left->right = new TreeNode(6);
37
38 Solution sol;
39 std::cout << "Floor of 5: " << sol.floorInBST(root, 5) << " (Expected: 4)\n";
40 std::cout << "Floor of 1: " << sol.floorInBST(root, 1) << " (Expected: -1)\n";
41 return 0;
42}

Time & Space Complexity

  • Time complexity: O(N)
  • Space complexity: O(N)

2. Recursive Binary Search Descent

Intuition

Directly follows BST branching rules. When moving right, the right subtree may or may not contain a value <= X; take the maximum of root.val and the right recursive call.

Algorithm

  1. If root is null, return -1.
  2. If root.val == X, return X.
  3. If root.val > X, return floorInBST(root.left, X).
  4. If root.val < X:
  5. Call rightFloor = floorInBST(root.right, X).
  6. Return rightFloor != -1 ? rightFloor : root.val.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2
3struct TreeNode {
4 int val;
5 TreeNode *left;
6 TreeNode *right;
7 TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
8};
9
10class Solution {
11public:
12 int floorInBST(TreeNode* root, int X) {
13 if (!root) return -1;
14 if (root->val == X) return X;
15 if (root->val > X) return floorInBST(root->left, X);
16
17 int rightFloor = floorInBST(root->right, X);
18 return (rightFloor != -1) ? rightFloor : root->val;
19 }
20};
21
22int main() {
23 TreeNode* root = new TreeNode(8);
24 root->left = new TreeNode(4);
25 root->right = new TreeNode(12);
26 root->left->left = new TreeNode(2);
27 root->left->right = new TreeNode(6);
28
29 Solution sol;
30 std::cout << "Recursive Floor 5: " << sol.floorInBST(root, 5) << " (Expected: 4)\n";
31 return 0;
32}

Time & Space Complexity

  • Time complexity: O(H)
  • Space complexity: O(H)

3. Iterative Binary Search Descent (O(1) Space)

Intuition

At each node: if curr.val == X, return X. If curr.val < X, update floorVal = curr.val and move curr = curr.right. If curr.val > X, move curr = curr.left. No stack needed.

Algorithm

  1. Initialize floorVal = -1, curr = root.
  2. While curr is not null:
  3. If curr.val == X:
  4. Return X (exact match is optimal floor).
  5. If curr.val < X:
  6. floorVal = curr.val;
  7. curr = curr.right;
  8. Else (curr.val > X):
  9. curr = curr.left;
  10. Return floorVal.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2
3struct TreeNode {
4 int val;
5 TreeNode *left;
6 TreeNode *right;
7 TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
8};
9
10class Solution {
11public:
12 int floorInBST(TreeNode* root, int X) {
13 int floorVal = -1;
14 TreeNode* curr = root;
15 while (curr) {
16 if (curr->val == X) {
17 return X;
18 }
19 if (curr->val < X) {
20 floorVal = curr->val;
21 curr = curr->right;
22 } else {
23 curr = curr->left;
24 }
25 }
26 return floorVal;
27 }
28};
29
30int main() {
31 TreeNode* root = new TreeNode(8);
32 root->left = new TreeNode(4);
33 root->right = new TreeNode(12);
34 root->left->left = new TreeNode(2);
35 root->left->right = new TreeNode(6);
36
37 Solution sol;
38 std::cout << "Iterative Floor 5: " << sol.floorInBST(root, 5) << " (Expected: 4)\n";
39 std::cout << "Iterative Floor 1: " << sol.floorInBST(root, 1) << " (Expected: -1)\n";
40 return 0;
41}

Time & Space Complexity

  • Time complexity: O(H)
  • Space complexity: O(1)

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Inorder Traversal Array ScanO(N)O(N)Collect all values via in-order traversal and linearly find last element <= X.Array allocation and full traversal
2.Recursive Binary SearchO(H)O(H)Recursive BST descent checking left or right depending on node comparison.Call stack depth
3.Iterative Binary SearchOptimalO(H)O(1)While-loop traversal updating floor candidate when moving right.Tree height

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Moving left when curr.val < X, which abandons potentially larger valid candidates.

Pitfall 2:

Overwriting floor candidate when moving left on curr.val > X.

Pitfall 3:

Forgetting the exact match case (curr.val == X) which allows immediate return.

Crucial Edge Cases to Validate:

  • X is smaller than the minimum value in the BST — floorVal remains initialized to -1 throughout the traversal, returning -1.
  • X equals an exact value present in the tree — Returns X immediately upon encountering curr.val == X.
  • X is greater than the maximum value in the BST — Traverses to the rightmost leaf and returns the maximum element.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Always explain the binary choice: curr.val < X means current node is a candidate and a better candidate might be on the right; curr.val > X means current node is too big so go left.
  2. Emphasize the contrast with Ceil: Floor tracks curr.val when going right, Ceil tracks curr.val when going left.
  3. Write the iterative solution immediately to demonstrate clean O(1) space traversal.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.What is the definition of Floor of X in a BST?

2.When curr.val < X, why do we move to curr.right?

3.What should be returned if all keys in the BST are strictly greater than X?

Back to DSA Sheet