Pattern visualizer

Inorder Successor in BST

The successor is either in p's right subtree (its minimum) or is the lowest ancestor of p reached by turning left. A single search from the root captures both cases without branching on them: every time p.val is smaller than the current node, that node is a candidate successor and the search continues left for something even closer; otherwise it moves right. Whatever candidate survives when the search runs off the tree is the answer. Animated on: root = [5,3,6,2,4,null,null,1], p = 3 — return the inorder successor of node p (the smallest value greater than p.val). Expected: 4..

Candidate tracking during a single root-to-target search

time O(h)space O(1)step 1 / 15

line 1

Find the inorder successor of p = 3 (marked "p"): the node holding the smallest value greater than p.val. There are no parent pointers, so search down from the root instead of scanning the whole tree.

Pseudocode

1FUNCTION inorderSuccessor(root, p):
2  successor <- null
3  curr <- root
4  WHILE curr != null:
5    IF p.val < curr.val:
6      successor <- curr
7      curr <- curr.left
8    ELSE:
9      curr <- curr.right
10  RETURN successor
11END FUNCTION

← / → step · space play · Home restart

Where to practice BST

Practice BST problems All BST problems Back to roadmap