LeetCode #285 Medium

Inorder Successor in BST

Return the node with the smallest value greater than p.val, or null.

bstbinary-search

02

Intuition

Successor = ceiling of p.val, exclusive. Walk from the root: going left past a node means that node is a successor candidate (it's bigger); going right discards. No parent pointers needed.

How to spot this pattern

The successor is the smallest value strictly greater than p — which is the ceil question in disguise. That's why no in-order traversal is needed: the BST ordering already tells you that going left tightens an upper bound. Recognising a problem as "nearest neighbour on one side" collapses it to a single O(h) walk.

03

Approach

1

Candidate on left turns

node.val > p.val → node might be the successor; remember it and go left for something tighter.

2

Discard on right turns

node.val ≤ p.val → successor must be right of here.

3

Classic alternative

If p has a right subtree, the successor is that subtree's leftmost node — the walk above covers both cases uniformly.

04

Solution & live demo

▶1class Solution:
▶2    def inorderSuccessor(self, root, p):
▶3        succ = None
▶4        node = root
▶5        while node:
▶6            if node.val > p.val:
▶7                succ = node             # candidate, try tighter
▶8                node = node.left
▶9            else:
▶10                node = node.right
▶11        return succ

05

Common pitfalls

Doing a full in-order traversal and taking the next node

✗ Wrong

vals = inorder(root)
i = vals.index(p.val)
return vals[i + 1]

✓ Right

while node:
    if node.val > p.val:
        succ = node
        node = node.left
    else:
        node = node.right

Correct, but O(n) time and O(n) space to answer a question the tree's shape already encodes. The walk is O(h) and allocates nothing.

Only looking inside p's right subtree

✗ Wrong

node = p.right
while node.left: node = node.left
return node

✓ Right

node = root
while node:
    if node.val > p.val:
        succ = node; node = node.left
    else:
        node = node.right

That handles only the case where p has a right child. When it doesn't, the successor is an ancestor — the last node you turned left at — and this version returns nothing or crashes. Walking from the root covers both cases with no branching.

06

Edge cases

p is the maximum

No left turn ever recorded → None.

Duplicates

Strict > comparison skips equal values correctly.

07

Complexity

Time

O(h)

Space

O(1)

One descent from the root.