Topics › Binary Search Trees › Practice Problems

Inorder successor and predecessor in BST

Medium TUF ID 103 SDE

Java source ↗ Edit this article ↗

Jump to code: Brute Better Optimal

Problem

You are given the root of a binary search tree with distinct positive keys and a value key. Return two numbers:

• the inorder predecessor: the largest key in the tree that is strictly smaller than key;
• the inorder successor: the smallest key in the tree that is strictly larger than key.

Report -1 for whichever one does not exist. The result is the pair {predecessor, successor}.

The names come from the inorder traversal, which lists a BST in sorted order: if key is in the tree, its predecessor and successor are simply its left and right neighbours in that sorted list. The definitions above also make sense when key is not in the tree, which some versions of the problem allow, and all methods here handle that case.

Constraints (typical, GeeksforGeeks version): up to 10^5 nodes, keys between 1 and 10^5. Because keys are positive, -1 can never be mistaken for a real key.

All examples use this tree:

           50
         /    \
       30      70
      /  \    /  \
     20  40  60  80
inorder: 20 30 40 50 60 70 80

Example 1

key = 50
answer = {40, 60}       // the neighbours of 50 in the sorted order

Example 2

key = 40
answer = {30, 50}       // 40 is a leaf; its successor 50 is an ancestor, not a descendant

Example 3

key = 65                // not in the tree
answer = {60, 70}

Approach 1: Brute force, inorder list and a scan

Intuition. The inorder traversal of a BST is sorted. Once the keys are in a sorted list, the predecessor is the last value below key and the successor is the first value above it. This ignores the tree shape completely, which makes it slow but easy to trust.

Algorithm.

1. Collect the inorder traversal into a list.
2. Scan it from left to right. Every value < key overwrites pred. The first value > key becomes succ, and the scan stops.
3. Return {pred, succ}.

static int[] bruteForce(TreeNode root, int key) {
    List<Integer> sorted = new ArrayList<>();
    collect(root, sorted);
    int pred = NONE, succ = NONE;
    for (int v : sorted) {
        if (v < key) pred = v;                               // last value below key wins
        else if (v > key) { succ = v; break; }               // first value above key wins
    }
    return new int[]{pred, succ};
}

static void collect(TreeNode node, List<Integer> out) {
    if (node == null) return;
    collect(node.left, out);
    out.add(node.val);
    collect(node.right, out);
}

Complexity. Time O(n) for the traversal; the scan is at most another O(n). Space O(n) for the list plus O(h) recursion.

Approach 2: Optimal, one descent with the subtree extremes

Intuition. Searching for key in a BST walks a single root-to-leaf path. Every node on that path is a useful candidate.

• When cur.val < key we go right. cur is smaller than key, so it is a possible predecessor. It is also larger than every candidate recorded earlier: each earlier predecessor candidate is an ancestor from which the walk went right, so cur lies in that ancestor’s right subtree and is larger than it. So overwriting pred with cur.val can only improve it. Everything in cur’s left subtree is smaller than cur, so nothing there can beat it, which is why skipping that subtree is safe.
• When cur.val > key we go left, and the mirror argument makes cur the best successor candidate so far.
• When cur.val == key the walk ends. The remaining candidates are inside key’s own subtrees: the largest key of the left subtree (its rightmost node) is closer than any ancestor candidate, and so is the smallest key of the right subtree (its leftmost node). If a subtree is empty, the ancestor candidate stands. That is exactly why Example 2 gives successor 50: node 40 has no right subtree, so the last ancestor at which we went left, 50, is the answer.

If key is not in the tree the walk simply falls off the bottom, and the recorded candidates are already the answer.

Algorithm.

1. pred = succ = -1, cur = root.
2. While cur != null:
   • cur.val < key: pred = cur.val, go right.
   • cur.val > key: succ = cur.val, go left.
   • Equal: if there is a left subtree, pred = its rightmost value; if there is a right subtree, succ = its leftmost value; stop.
3. Return {pred, succ}.

static int[] oneDescent(TreeNode root, int key) {
    int pred = NONE, succ = NONE;
    TreeNode cur = root;
    while (cur != null) {
        if (cur.val < key) {                                 // candidate predecessor, look for a larger one
            pred = cur.val;
            cur = cur.right;
        } else if (cur.val > key) {                          // candidate successor, look for a smaller one
            succ = cur.val;
            cur = cur.left;
        } else {                                             // found key: neighbours are inside its subtrees, if any
            if (cur.left != null) {
                TreeNode t = cur.left;
                while (t.right != null) t = t.right;         // maximum of the left subtree
                pred = t.val;
            }
            if (cur.right != null) {
                TreeNode t = cur.right;
                while (t.left != null) t = t.left;           // minimum of the right subtree
                succ = t.val;
            }
            break;
        }
    }
    return new int[]{pred, succ};
}

Complexity. Time O(h): the main walk and the subtree walks together move strictly downward, so they visit at most h + 1 nodes. Space O(1).

Approach 3: Optimal variant, two independent descents

Intuition. Approach 2 needs a special case for “found it”. We can avoid it by computing each answer with its own walk and folding equality into one of the branches.

For the successor: at each node, if cur.val > key it is a candidate, and a better (smaller) candidate can only be in its left subtree, so record it and go left. Otherwise (cur.val <= key) the node and its entire left subtree are too small, so go right. When cur.val == key, going right leads to the leftmost node of the right subtree, which is exactly what Approach 2 computes explicitly. The predecessor walk is the mirror image. Each walk is a “best candidate on the search path” loop, the same pattern used for floor and ceil.

Algorithm.

1. successor: best = -1; walk from the root; if cur.val > key set best = cur.val and go left, else go right.
2. predecessor: best = -1; walk from the root; if cur.val < key set best = cur.val and go right, else go left.
3. Return {predecessor, successor}.

static int[] twoDescents(TreeNode root, int key) {
    return new int[]{predecessor(root, key), successor(root, key)};
}

static int predecessor(TreeNode root, int key) {
    int best = NONE;
    for (TreeNode cur = root; cur != null; ) {
        if (cur.val < key) {
            best = cur.val;                                  // valid, and everything left of it is smaller still
            cur = cur.right;
        } else {
            cur = cur.left;                                  // too big (or equal): answer is further left
        }
    }
    return best;
}

static int successor(TreeNode root, int key) {
    int best = NONE;
    for (TreeNode cur = root; cur != null; ) {
        if (cur.val > key) {
            best = cur.val;
            cur = cur.left;
        } else {
            cur = cur.right;
        }
    }
    return best;
}

Dry run for key = 40 (Example 2):

Result {30, 50}.

Complexity. Time O(h): two walks of at most h + 1 nodes each. Space O(1). It does about twice the work of Approach 2 in the worst case but has no special case, so it is harder to get wrong.

Edge cases and pitfalls

• Strict inequalities. The predecessor must be strictly smaller and the successor strictly larger. Using <= in the predecessor walk would return key itself when it is present.
• Smallest and largest keys. The smallest key has no predecessor and the largest has no successor; both report -1. Keys below or above every value in the tree behave the same way.
• Ancestor answers. For a node without a right subtree, the successor is an ancestor (Example 2). A method that only looks inside the found node’s subtrees misses this. The tests include a case where the successor is two levels up.
• Key not present. Approaches 2 and 3 handle it with no extra code; Example 3 and an odd key in a tree of even keys test it.
• Empty tree. All methods return {-1, -1}.
• Sentinel choice. -1 is safe only because keys are positive. If keys can be negative, return Integer values with null, or a long sentinel outside the int range.
• Skewed trees. O(h) becomes O(n) when the BST is a chain; the bound is only O(log n) for balanced trees.

Related problems

• Inorder Successor/Predecessor in BST is the same problem in the A2Z sheet.
• Floor and Ceil in a BST are the non-strict versions (≤ and ≥) of the same two walks.
• Floor in a BST and Ceil in a BST treat each half separately.
• BST iterator returns successors one after another in amortised O(1).
• Search in BST is the plain downward walk these methods extend.
• Inorder Traversal gives the sorted order that Approach 1 scans.