Inorder Successor in BST

You are given the root of a binary search tree whose values are all distinct, and a node p that belongs to the tree. Return the in-order successor of p: the node holding the smallest value that is strictly greater than p.val. If p holds the largest value in the tree, return null.

The tree is given as a level-order array with null for missing children. In the test data, p is written as its value; the judge passes your function the actual node with that value. The judge checks the value of the node you return.

Example 1

Example 2

Example 3

Constraints

• 1 <= number of nodes <= 104
• -105 <= Node.val <= 105
• All values are unique, and p is a node of the tree.

Pattern Path · Binary Search Trees · problem 102 of 169

Start simple

Do a full in-order traversal into a list and return the element after p: O(n) time and O(n) space.

The key idea

The successor is the smallest value strictly greater than p.val, which is a search question, and a BST is built for search. Start at the root and keep one variable, successor.

• If node.val > p.val, this node is greater than p, so it could be the answer. Remember it, then move left, because any better answer must be smaller than this node.
• Otherwise the node (and its whole left subtree) is too small, so move right.

Each step discards one subtree that cannot contain a better answer, and every value greater than p.val that could beat the current candidate stays on the path. When the walk ends, successor holds the smallest value greater than p.val, or null if none exists.

This one loop covers both textbook cases: if p has a right subtree the walk ends at that subtree's leftmost node, and if not, the answer is the last ancestor where the path turned left. No parent pointers or extra memory are needed.

Complexity

• Time: O(h)
• Space: O(1)

Python

class Solution:
    def inorderSuccessor(self, root, p):
        successor = None
        node = root
        while node:
            if node.val > p.val:
                successor = node  # candidate; a smaller one can only be on the left
                node = node.left
            else:
                node = node.right
        return successor

JavaScript

var inorderSuccessor = function(root, p) {
  let successor = null;
  let node = root;
  while (node) {
    if (node.val > p.val) {
      successor = node; // candidate; a smaller one can only be on the left
      node = node.left;
    } else {
      node = node.right;
    }
  }
  return successor;
};

What the interviewer is checking

It checks whether you use the BST ordering to search in O(h) instead of falling back to a full traversal, and whether you handle the no-right-subtree case without parent pointers.

Mistakes to avoid

• Only checking p.right: when p has no right subtree the successor is an ancestor, not null.
• Using >= instead of >, which returns p itself.
• Traversing the whole tree into a list, which is O(n) when O(h) is possible.
• Forgetting to return null for the maximum node.

Follow-ups to expect

• Find the in-order predecessor instead. (Mirror the comparisons.)
• What if nodes had parent pointers and you had no root? (Climb until coming from a left child.)
• Iterate the whole BST in order with O(h) memory. (Stack-based BST iterator.)

In real software

Ordered maps built on balanced trees (such as a tree map's higher-key lookup) answer "next key after this one" with exactly this walk, which is how range scans and cursor pagination step forward.

Practice next