Floor in BST

Medium
1970.

Floor in BST

Floor in BST is a medium coding problem on binary search and trees, asked in Amazon and Samsung interviews.

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^5
  • 1 <= Node.val <= 10^5
  • all node values are distinct
  • 1 <= x <= 10^5

Follow-up: Can you do it in O(height) time without visiting the whole tree?

Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * Definition for a binary tree node (provided by the judge — do not redefine it):
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} x
 * @return {number}
 */
var floor = function(root, x) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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^5
  • 1 <= Node.val <= 10^5
  • all node values are distinct
  • 1 <= x <= 10^5

Follow-up: Can you do it in O(height) time without visiting the whole tree?

Hints for Floor in BST

  1. Hint 1

    Compare x with the current node: the answer can only lie on one side of it.

  2. 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.

  3. 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

  1. Set best = -1 and start at the root.
  2. If the node's value equals x, return x.
  3. If it is smaller than x, set best to it and move to the right child.
  4. If it is larger, move to the left child.
  5. 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 x is wrong — a larger one may still sit in its right subtree.
  • Return -1 only 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 best

Java

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