Inorder Successor in BST

Medium Trees & BST Miscellaneous BST Questions Original on LeetCode

Inorder Successor in BST is a medium trees & bst problem solved with the miscellaneous bst questions pattern. The best approach, optimal (walk down with a candidate), runs in O(h) time and O(1) space. Below are 2 approaches in Java, from inorder list up.

Problem

Given a BST and a node p, return its inorder successor: the node with the smallest value greater than p.val, or null if there is none.

Examples

Example 1

Input: root = [5, 3, 6, 2, 4, null, null, 1], p = 4
Output: 5

Example 2

Input: same tree, p = 6
Output: null
Why: 6 is the largest value.

Constraints

The tree has 1 to 10^4 nodes; unique values; p is in the tree.

Animated walkthrough

A narrated, step-by-step animation that builds the solution from the idea up. Press play, or step through it at your own pace.

Concepts first, then the problem and every approach, step by step.

Code

Code appears here once we start writing it.

Space to play or pause · ← → to jump a step · click or drag the bar to seek

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the Java code.

Approach	Time	Space
Inorder list	`O(n)`	`O(n)`
Optimal (walk down with a candidate)	`O(h)`	`O(1)`

1Inorder list

TimeO(n)

SpaceO(n)

Collect the inorder traversal and return the node right after p.

Inorder into a list of nodes; find p; return the next one.

Java

class Solution {
    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        List<TreeNode> nodes = new ArrayList<>();
        inorder(root, nodes);
        for (int i = 0; i + 1 < nodes.size(); i++) if (nodes.get(i) == p) return nodes.get(i + 1);
        return null;
    }

    private void inorder(TreeNode n, List<TreeNode> out) {
        if (n == null) return;
        inorder(n.left, out);
        out.add(n);
        inorder(n.right, out);
    }
}

2Optimal (walk down with a candidate)

TimeO(h)

SpaceO(1)

From the root: if node.val > p.val, this node is a possible successor, so remember it and go left to find a smaller one. Otherwise go right. The last remembered node is the answer.

succ = null; cur = root.
If cur.val > p.val: succ = cur; cur = cur.left. Else cur = cur.right.

Java

class Solution {
    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        TreeNode succ = null, cur = root;
        while (cur != null) {
            if (cur.val > p.val) { succ = cur; cur = cur.left; }
            else cur = cur.right;
        }
        return succ;
    }
}

Edge cases to test

p is the maximum (no successor)
p has a right subtree
p has no right subtree (the successor is an ancestor)

Hints

Hint 1

The successor is the smallest value greater than p. Walk from the root: going left records a candidate.

FAQ

What is the best time complexity for Inorder Successor in BST?

Optimal (walk down with a candidate) runs in O(h) time and O(1) extra space.

Which pattern does Inorder Successor in BST use?

It is a trees & bst problem that uses the miscellaneous bst questions pattern. Other problems with the same pattern: Inorder predecessor, Floor in BST, Ceil in BST.

Is there a brute force solution for Inorder Successor in BST?

Yes. Inorder list takes O(n) time and O(n) space. Collect the inorder traversal and return the node right after p.

Which edge cases should I test for Inorder Successor in BST?

p is the maximum (no successor); p has a right subtree; p has no right subtree (the successor is an ancestor).