Which Stored Value Comes Right Before a Key

Medium20–25 min

Topics

Binary Search TreeBSTInorder PredecessorSearch

Companies

AmazonMicrosoftFacebookGoogleFlipkart

You are given the root of a binary search tree with distinct values and an integer key (the key need not be in the tree). Return the value that comes immediately before key in the ascending order of the tree's values — the largest value strictly smaller than key — or -1 if no value is smaller.

A list of all values makes this a simple scan. Walking down the tree once and remembering the last node where you turned right finds it directly.

Test Case 1:

Input:root = [42, 18, 66, 9, 30, 54, 80, null, null, 24, 36, null, 60], key = 36

Output:30

Explanation:In sorted order (…, 24, 30, 36, 42, …) the value right before 36 is 30 — the closest ancestor for which 36 lies in the right subtree.

Test Case 2:

Input:root = [42, 18, 66, 9, 30, 54, 80, null, null, 24, 36, null, 60], key = 42

Output:36

Explanation:42 has a left subtree; the value before it is the rightmost node of that subtree, 36.

Test Case 3:

Input:root = [42, 18, 66, 9, 30, 54, 80, null, null, 24, 36, null, 60], key = 9

Output:-1

Explanation:9 is the smallest value: nothing comes before it.

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
◆key is any integer between 0 and 1000 (it does not have to be in the tree)
◆Return the value that comes immediately before key when the tree's values are listed in ascending order — that is, the largest value that is STRICTLY smaller than key. If there is none, 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, Keep the Last One Below the Key

Brute

An inorder walk gives the values in ascending order. Collect them in a list and scan it, remembering the last value that is strictly smaller than the key; because the list ascends, that last value is the one that comes right before the key. If nothing is smaller, the answer stays -1. It walks all n nodes and stores all n values: O(n) time and O(n) space.

TimeO(n)

SpaceO(n)

Java

Try it out

class Solution {
    public int predecessorOf(TreeNode root, int key) {
        List<Integer> vals = new ArrayList<>();
        inorder(root, vals);
        int best = -1;
        for (int v : vals) {
            if (v < key) 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 — Descend Once, Remembering the Last Node Where We Turned Right

Optimal

Walk down from the root. If the current node's value is smaller than the key, it is a candidate for "the value just before the key" — remember it — and a larger candidate (still below the key) could only be in its RIGHT subtree, so go right. If the current node's value is not smaller than the key, neither it nor anything on its right can qualify, so go LEFT. When the path ends, the last remembered candidate is the predecessor (or -1). This handles both cases at once: the rightmost node of the key's left subtree, or the nearest ancestor from which the path turned right. O(h) time, O(1) space.

TimeO(h)

SpaceO(1)