PPractick

The problem

A booking system stores available start times in a BST and, for a requested time, must offer the latest available slot not after it: the floor, meaning the largest key ≤ x, or −1 if every slot is later. The recursive formulation reads like the definition. If the node equals x, it's the answer. If the node is larger than x, the floor must be in the left subtree. If it's smaller, this node is a candidate, but a larger valid key might exist in the right subtree, so use that if it exists, else this node.

Example: BST [5, 2, 12, 1, 3, 9, 21, null, null, null, null, null, null, 19, 25], x = 13 → 12.

Function signature

int floorBST(TreeNode* root, int x);  // -1 if every key is greater than x

Test cases

Input (tree, x)	Output	Explanation
([5,2,12,1,3,9,21,null,null,null,null,null,null,19,25], 13)	12
(same tree, 4)	3
(same tree, 20)	19
(same tree, 25)	25	An exact match
(same tree, 0)	-1	Every key is larger

(Confirm: keys are distinct and positive, so −1 can mean "no floor".)

How interviewers phrase it

• "Given a BST and a number x, find the floor of x: the greatest value in the BST that is less than or equal to x" (GeeksforGeeks "Floor in BST").

Clarifying questions to ask

1. ≤ or strictly <? (≤, so an exact match is the answer.)
2. What should be returned if there's none? (−1.)
3. Recursive or iterative? (Recursive here; the iterative walk is the same idea.)

Follow-ups to expect

1. "Why does a node larger than x send you left only?"
2. "Why check the right subtree when the node is smaller?"
3. "How do you combine?"
4. "Ceil?"
5. "Complexity?"

Related questions

• Search in a Binary Search Tree Easy
• Floor and Ceil in a BST Easy
• Insert a given node in BST Medium
• Delete a node in BST Medium
• Check if a tree is a BST or not Medium
• LCA in BST Medium

All 474 dsa interview questions

DSA mock interviews · System design interview questions · Free mock interview practice · Browse interviewers · Sign in