AlgoMaster Logo

Inorder Successor in BST

mediumFrequencyUpdated September 21, 2026

Understanding the Problem

We have a binary search tree and a reference to a specific node p in that tree. We need to find the node that comes immediately after p in an in-order traversal. In-order traversal of a BST visits nodes in ascending order, so the in-order successor is the node with the smallest value that is strictly greater than p.val.

There are two distinct cases. If p has a right subtree, the successor is the leftmost node in that right subtree, because that is the smallest value greater than p within p's own descendants. If p has no right subtree, the successor is the closest ancestor for which p falls in the left subtree. These two cases drive every approach to this problem.

Key Constraints:

  • Number of nodes in [1, 10^4] -- An O(n) solution runs comfortably, but the BST structure lets us aim for O(h) where h is the height.
  • -10^5 <= Node.val <= 10^5 -- Values fit in a 32-bit integer, so comparisons have no overflow concerns.
  • All Nodes will have unique values -- With no duplicates, a strict greater-than comparison is enough to identify the successor.

Approach 1: Inorder Traversal

Intuition

Perform a full in-order traversal, collect all nodes in sorted order, then return the one right after p. Because in-order traversal of a BST produces nodes in ascending order, the successor of p is the next node in that sequence.

This ignores the BST property as a navigation tool, but it is easy to reason about and serves as a baseline.

Algorithm

  1. Perform an in-order traversal of the entire BST and store all nodes in a list.
  2. Iterate through the list to find node p.
  3. If p is found at index i and i + 1 is within bounds, return the node at index i + 1.
  4. If p is the last node in the list, return null (no successor exists).

Visualization and Code

Loading animation...

This visits every node and stores them all before searching. The next approach stops the traversal as soon as the successor appears, avoiding both the full scan and the extra list.

Approach 2: Optimized Inorder Traversal (Early Termination)

Intuition

Instead of collecting every node and then searching, run the in-order traversal and stop the moment we move past p. Because the traversal visits nodes in ascending order, the first node visited after p is its successor.

We still do an in-order traversal, but we short-circuit once the answer is known. When p sits near the start of the in-order sequence, only a few nodes get visited before the traversal returns.

Algorithm

  1. Perform an in-order traversal of the BST.
  2. Use a flag to track when we've visited p. Once we've visited p, the very next node in the traversal is our answer.
  3. Return that next node immediately, stopping the traversal.
  4. If the traversal completes without finding a successor, return null.

Visualization and Code

Loading animation...

Early termination still ignores the BST property for navigation. The next approach uses value comparisons to walk a single root-to-leaf path, reaching the answer in O(h) time.

Approach 3: BST Property (Optimal)

Intuition

The BST property lets us walk a single path from the root downward, making a binary-search-style decision at each node instead of traversing the whole tree.

Walk down from the root and compare each node's value to p.val. When a node's value is greater than p.val, it is a candidate successor, so record it and move left to look for an even smaller value that is still greater than p.val. When a node's value is less than or equal to p.val, it cannot be the successor, so move right.

When the walk reaches null, the last recorded candidate is the answer. This covers both cases. If p has a right subtree, the walk eventually enters it and descends to its leftmost node. If p has no right subtree, the last left turn before reaching p recorded the correct ancestor.

The recorded candidate is always the smallest value greater than p.val seen so far, because each left move only replaces it with a value that is both greater than p.val and smaller than the previous candidate. Discarding everything to the right of a candidate is safe, since those values are all larger.

Algorithm

  1. Initialize successor = null.
  2. Start at the root.
  3. If the current node's value is greater than p.val, update successor to this node and move left (looking for a smaller valid candidate).
  4. If the current node's value is less than or equal to p.val, move right (current node is too small to be a successor).
  5. When the current node becomes null, return successor.

Visualization and Code

Loading animation...