Floor in BST — Solution in Python, Java & C++
Floor in BST solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem on binary search and trees.
Floor in BST is a medium coding problem on binary search and trees, asked in Amazon and Samsung interviews.
- Difficulty: Medium
- Topics: Binary Search, Trees
- Asked at: Amazon, Samsung
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given the root of a binary search tree with distinct values and an integer x.
Return the floor of x in the tree: the largest node value that is less than or equal to x. If every value in the tree is greater than x, return -1.
Example 1
Input: root = [2,1,81,null,null,42,87,null,66,null,null,45], x = 87
Output: 87
Explanation: 87 is in the tree, so it is its own floor.
Example 2
Input: root = [6,null,8,7,9], x = 11
Output: 9
Explanation: Every value is at most 11; the largest is 9.
Example 3
Input: root = [10,5,15,2,7], x = 1
Output: -1
Explanation: Nothing in the tree is 1 or smaller.
Constraints
1 <= number of nodes <= 10^51 <= Node.val <= 10^5all node values are distinct1 <= x <= 10^5
Follow-up: Can you do it in O(height) time without visiting the whole tree?
Hints for Floor in BST
Hint 1
Compare
xwith the current node: the answer can only lie on one side of it.Hint 2
If the node's value is greater than
x, it cannot be the floor, and neither can anything in its right subtree — go left.Hint 3
If the node's value is at most
x, it is a candidate; a better (larger) candidate can only be in its right subtree. Remember it and go right.
How to solve Floor in BST
Walk down from the root like a search for x, remembering the last value that was not larger than x. That remembered value is the floor.
Approach
- Set
best = -1and start at the root. - If the node's value equals
x, returnx. - If it is smaller than
x, setbestto it and move to the right child. - If it is larger, move to the left child.
- When the walk falls off the tree, return
best.
Why it works
Going left from a value larger than x discards only values larger than x. Going right from a candidate discards only values smaller than that candidate, which cannot beat it. So the floor is never discarded, and each candidate recorded is larger than the previous one; the last is the floor.
Complexity
- Time —
O(h), h the height of the tree - Space —
O(1)
Pitfalls
- Stopping at the first value below
xis wrong — a larger one may still sit in its right subtree. - Return
-1only when no candidate was ever recorded.
Reference solution
Python
from typing import Optional
def floor(root: Optional[TreeNode], x: int) -> int:
best = -1
node = root
while node:
if node.val == x:
return x
if node.val < x:
best = node.val
node = node.right
else:
node = node.left
return bestJava
public static int floor(TreeNode root, int x) {
int best = -1;
TreeNode node = root;
while (node != null) {
if (node.val == x) return x;
if (node.val < x) { best = node.val; node = node.right; }
else node = node.left;
}
return best;
}C++
int floor(TreeNode* root, int x) {
int best = -1;
TreeNode* node = root;
while (node) {
if (node->val == x) return x;
if (node->val < x) { best = node->val; node = node->right; }
else node = node->left;
}
return best;
}JavaScript
var floor = function(root, x) {
var best = -1, node = root;
while (node !== null) {
if (node.val === x) return x;
if (node.val < x) { best = node.val; node = node.right; }
else node = node.left;
}
return best;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 189 binary search problems · the whole catalogue
Learn the technique: Binary Search · Binary Trees and Tree Traversals