Skip to main content

510 - Inorder Successor in BST II

Difficulty: Medium | Pattern: Tree Navigation | Company tags: Facebook, Amazon

Problem Statement​

Given a node in a BST, return the in-order successor of that node in the BST. If there is no in-order successor, return null.

The successor of a node p is the node with the smallest key greater than p.val.

You will have direct access to the node but not to the root of the tree. Each node has a parent pointer in addition to left and right.

Approach: O(h), O(1)​

Case 1: Node has a right subtree → successor is the leftmost node in the right subtree.

Case 2: Node has no right subtree → go up via parent pointers until we come from a left child. That ancestor is the successor.

def inorderSuccessor(node) -> 'Node':
    # Case 1: right subtree exists
    if node.right:
        node = node.right
        while node.left:
            node = node.left
        return node
    
    # Case 2: no right subtree — go up until we came from a left child
    while node.parent and node == node.parent.right:
        node = node.parent
    return node.parent

Algorithm Flow​

Dry Run​

    5
   / \
  3   6
 / \
2   4

inorderSuccessor(4):

  • node=4, no right subtree
  • node==parent.right (4 is right child of 3) → go up to 3
  • node==parent.left (3 is left child of 5) → stop
  • Return node.parent = 5 ✓

inorderSuccessor(6):

  • node=6, no right subtree
  • node==parent.right (6 is right child of 5) → go up to 5
  • node.parent = None → return None ✓ (6 is the max)

Why This Works​

Inorder traversal is left → root → right. After visiting a node:

  • If it has a right child, the next node is the minimum of the right subtree.
  • Otherwise, we came up from the right and need to keep going up until we find an ancestor where we arrived from the left.

Complexity​

  • Time: O(h) — height of tree
  • Space: O(1)

Key Terms​

TermDefinition
Inorder successorThe node visited immediately after a given node in an inorder (left-root-right) traversal; the smallest key greater than it.
Parent pointerA back-reference from child to parent that lets a node navigate upward without access to the tree's root.
Leftmost nodeThe node reached by repeatedly following .left from a subtree's root; it holds the subtree's minimum value.
BST propertyLeft subtree values are smaller and right subtree values are larger than the current node, enabling O(h) navigation.

FAQ​

  1. Can this be solved without extra space? Yes — the parent-pointer approach already runs in O(1) extra space and O(h) time, since it only follows existing pointers.
  2. What if the given node has no successor (it's the maximum)? The upward walk exits the loop when node.parent becomes None, and the function correctly returns null.
  3. How would this change if there were no parent pointers (LeetCode 285)? Without parent pointers you'd need the root and a standard BST search, tracking the last ancestor for which you went left as the candidate successor.
  4. What if the node has a right subtree? The successor is simply the leftmost (minimum) node of that right subtree — no need to check parent pointers at all in that case.
  5. Does this rely on the BST ordering property, or would it work on any binary tree? It relies entirely on BST ordering — the "go right then leftmost" and "go up while a right child" rules are only valid because of the left < node < right invariant.

Quick Revision​

  • Problem: find the inorder successor of a node in a BST using only parent, left, right pointers (no root access).
  • Case 1: node has a right subtree → successor is the leftmost node of that subtree.
  • Case 2: node has no right subtree → walk up via parent while the current node is a right child.
  • Stop walking up when you arrive from a left child, or when parent is null (no successor).
  • Successor of the max node is null since there's nothing greater.
  • No extra data structures needed — pure pointer traversal, O(1) space.
  • Time is O(h), bounded by tree height, not total node count.
  • Contrast with LeetCode 285 (same problem but with root access instead of parent pointers).