Which Stored Value Comes Right After a Key

Medium20–25 min

Topics

Binary Search TreeBSTInorder SuccessorSearch

Companies

AmazonMicrosoftFacebookGoogleBloomberg

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 after key in the ascending order of the tree's values — the smallest value strictly greater than key — or -1 if no value is greater.

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

Test Case 1:

Input:root = [35, 15, 60, 8, 25, 45, 75, null, null, 20, 30, null, 50], key = 25

Output:30

Explanation:In sorted order (8, 15, 20, 25, 30, 35, …) the value right after 25 is 30 — the leftmost node of 25's right subtree.

Test Case 2:

Input:root = [35, 15, 60, 8, 25, 45, 75, null, null, 20, 30, null, 50], key = 30

Output:35

Explanation:30 has no right subtree, so the next value is the closest ancestor for which 30 lies in the left subtree: 35.

Test Case 3:

Input:root = [35, 15, 60, 8, 25, 45, 75, null, null, 20, 30, null, 50], key = 75

Output:-1

Explanation:75 is the largest value: nothing comes after 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 after key when the tree's values are listed in ascending order — that is, the smallest value that is STRICTLY greater 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, Take the First One Above the Key

Brute

An inorder walk gives the tree's values in ascending order. Collect them in a list and scan from the smallest: the first value that is strictly greater than the key is the one that comes right after it (whether or not the key itself is in the tree). If none is greater, the answer is -1. It walks 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 successorOf(TreeNode root, int key) {
        List<Integer> vals = new ArrayList<>();
        inorder(root, vals);
        for (int v : vals) {
            if (v > key) return v;
        }
        return -1;
    }

    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 Left

Optimal

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

TimeO(h)

SpaceO(1)