Largest Stored Value That Does Not Exceed a Number

Medium20–25 min

Topics

Binary Search TreeBSTFloorSearch

Companies

AmazonMicrosoftFlipkartSamsung

You are given the root of a binary search tree with distinct values and an integer x. Return the largest value in the tree that is less than or equal to x (the "floor" of x). If every value in the tree is larger than x, or the tree is empty, return -1.

Listing all values in order works, but the search-tree property lets you find the answer by walking one path from the root, remembering the best candidate so far.

Test Case 1:

Input:root = [55, 30, 80, 15, 45, 65, 95, null, null, 40, 50], x = 48

Output:45

Explanation:The values ≤ 48 are 15, 30, 40 and 45; the largest of them is 45 (50 is already too big).

Test Case 2:

Input:root = [55, 30, 80, 15, 45, 65, 95, null, null, 40, 50], x = 10

Output:-1

Explanation:The smallest value in the tree is 15, which is more than 10.

Test Case 3:

Input:root = [55, 30, 80, 15, 45, 65, 95, null, null, 40, 50], x = 65

Output:65

Explanation:x itself is in the tree, and equal counts.

Constraints

◆0 ≤ number of nodes ≤ 100; all node values are distinct, 0 ≤ node.val ≤ 1000
◆The tree is a binary search tree (left subtree smaller, right subtree larger at every node), given by its root node
◆0 ≤ x ≤ 1000
◆Return the largest value in the tree that is less than or equal to x (x itself counts). If every value is larger than x, or the tree is empty, return -1

🚀

Try the Dry Run

Don't just read the solution — watch it execute, one step at a time.

Approach & Solutions

Brute Force — List All Values in Order, Then Scan

Brute

An inorder walk of a binary search tree visits the values in ascending order. Collect them all in a list, then scan it and remember the last value that is still ≤ x; because the list is ascending, that last value is the largest one not exceeding x. It is correct but always touches every node and stores all n values: O(n) time and O(n) space.

TimeO(n)

SpaceO(n)

Java

Try it out

class Solution {
    public int floorOf(TreeNode root, int x) {
        List<Integer> vals = new ArrayList<>();
        inorder(root, vals);
        int best = -1;
        for (int v : vals) {
            if (v <= x) best = v;
        }
        return best;
    }

    private void inorder(TreeNode node, List<Integer> vals) {
        if (node == null) return;
        inorder(node.left, vals);
        vals.add(node.val);
        inorder(node.right, vals);
    }
}

Optimal — Walk Down Once, Remembering the Best Candidate

Optimal

Walk down from the root, keeping best = the largest value seen so far that is ≤ x (initially -1). If the current node equals x, that is the answer. If it is smaller than x, it is a valid candidate — record it — and anything better must be larger, so go to the RIGHT. If it is larger than x it is too big, and all of its right subtree is bigger still, so go LEFT. When the walk runs off the tree, best holds the answer. Only one root-to-leaf path is followed: O(h) time, O(1) space.

TimeO(h)

SpaceO(1)