DSA Tracker

Visualize

Inorder Successor in BST

Candidate tracking during a single root-to-target search

time O(h)space O(1)

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.

Details

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.

Problem:Inorder Successor in BSTMedium

Candidate tracking during a single root-to-target search

step 1 / 15

1
2
3
p
4
5
6

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

Every step in words

Show all 15 steps
  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.
  2. Start: successor = null, curr = root (5).
  3. curr (5) is not null, so the loop continues. Compare p.val (3) to curr.val (5).
  4. 3 < 5, so curr (5) is bigger than p — it's a valid candidate successor.
  5. successor <- 5. It is the smallest node seen so far that is still bigger than p, so it's the current best answer.
  6. Searching further left might find something even smaller than 5 but still greater than p, so curr <- 3.
  7. curr (3) is not null, so the loop continues. Compare p.val (3) to curr.val (3).
  8. 3 >= 3, so curr (3) is p itself or smaller — it can never be the successor. Move right without touching successor.
  9. curr <- 4.
  10. curr (4) is not null, so the loop continues. Compare p.val (3) to curr.val (4).
  11. 3 < 4, so curr (4) is bigger than p — it's a valid candidate successor.
  12. successor <- 4. It is the smallest node seen so far that is still bigger than p, so it's the current best answer.
  13. curr.left is null, so curr becomes null and the loop ends.
  14. curr is now null, so the loop exits.
  15. RETURN successor. The inorder successor of 3 is 4. Only h nodes on the root-to-target path were ever visited, so this runs in O(h), not O(n).

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Inorder Successor in BST in the editorAll BST problemsBack to roadmap