☕ DSA Java Articles

Topics › Binary Search Trees › Practice Problems

Inorder Successor/Predecessor in BST

Medium TUF ID 2775 A2Z

Java source ↗ Edit this article ↗

Problem

You are given the root of a binary search tree and a key. Return two values:

If either one does not exist, report -1 for it. The result is {predecessor, successor}. When key is in the tree these are simply its neighbours in the in-order (sorted) sequence; the definition above also works when key is not in the tree, which some versions of the problem allow. Keys are positive here, so -1 cannot be confused with a real key. Constraints: up to 10^5 nodes.

All examples use this tree:

        5
      /   \
     2     10
    / \   /  \
   1   4 7    12
in-order: 1 2 4 5 7 10 12

Example 1

key = 10
answer = {7, 12}      // neighbours of 10 in the sorted sequence

Example 2

key = 4
answer = {2, 5}       // the successor 5 is an ancestor of 4, not a descendant

Example 3

key = 6
answer = {5, 7}       // 6 is not in the tree; 5 is the largest key below it, 7 the smallest above

Approach 1: Brute force, read the sorted sequence

Intuition. The in-order traversal of a BST lists its keys in ascending order. Once we have that list, the predecessor is the last key below key and the successor is the first key above it. A single scan finds both. This ignores the tree’s shape entirely, so it does a full traversal even though the answer sits near one path.

Algorithm.

  1. Collect the keys with an in-order traversal.
  2. Scan left to right. Every key below key overwrites pred, so the last one wins. The first key above key is succ, and the scan can stop there.
  3. Return {pred, succ}, with -1 for anything not found.
static int[] bruteForce(TreeNode root, int key) {
    List<Integer> sorted = new ArrayList<>();
    collectInorder(root, sorted);
    int pred = NONE, succ = NONE;
    for (int v : sorted) {
        if (v < key) pred = v;                       // keeps overwriting: the last one below key wins
        else if (v > key) { succ = v; break; }       // the first one above key is the answer
    }
    return new int[]{pred, succ};
}

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

Complexity. Time O(n) for the traversal. Space O(n) for the list, plus O(h) recursion.

Approach 2: Optimal, one root-to-leaf walk per answer

Intuition. Searching for the successor is a binary search for “the smallest key that is greater than key”. Stand at a node cur:

Every time we record, we then move into the left subtree of the recorded node, so each new candidate is smaller than the previous one. When we fall off the tree, the last recorded value is the smallest key above key. The predecessor is the mirror image: record when cur.val < key and go right; otherwise go left.

The textbook version needs parent pointers: “if the node has a right subtree, take its leftmost node; otherwise climb to the first ancestor of which the node is in the left subtree”. The walk from the root covers both cases. In the second case the ancestor was recorded on the way down, and in the first case the walk continues into the right subtree and records its leftmost path.

Algorithm.

  1. successor: start at the root with succ = -1. If cur.val > key, set succ = cur.val and go left; else go right. Stop at null.
  2. predecessor: start at the root with pred = -1. If cur.val < key, set pred = cur.val and go right; else go left.
  3. Return {predecessor, successor}.
static int[] optimal(TreeNode root, int key) {
    return new int[]{predecessor(root, key), successor(root, key)};
}

static int successor(TreeNode root, int key) {
    int succ = NONE;
    TreeNode cur = root;
    while (cur != null) {
        if (cur.val > key) {
            succ = cur.val;          // a candidate; anything smaller that still beats key is on the left
            cur = cur.left;
        } else {
            cur = cur.right;         // cur and its whole left subtree are <= key
        }
    }
    return succ;
}

static int predecessor(TreeNode root, int key) {
    int pred = NONE;
    TreeNode cur = root;
    while (cur != null) {
        if (cur.val < key) {
            pred = cur.val;          // a candidate; anything larger that is still below key is on the right
            cur = cur.right;
        } else {
            cur = cur.left;          // cur and its whole right subtree are >= key
        }
    }
    return pred;
}

Dry run for the successor of 4:

cur cur.val > 4? succ move
5 yes 5 left to 2
2 no 5 right to 4
4 no 5 right to null

The answer is 5, an ancestor, which the “leftmost node of the right subtree” rule alone would miss because 4 has no right subtree.

And for the predecessor of 10:

cur cur.val < 10? pred move
5 yes 5 right to 10
10 no 5 left to 7
7 yes 7 right to null

The answer is 7.

Complexity. Time O(h): each walk descends one level per step, O(log n) for a balanced tree and O(n) for a chain. Space O(1): two loops with one pointer each.

These two walks are exactly the “ceil” and “floor” searches on a BST, with strict comparisons in place of >= and <=. Because the comparison is strict, a node whose key equals key is skipped automatically, which is what makes the method work whether or not key is present.

Edge cases and pitfalls