Inorder Successor in BST II — With Parent Pointers in O(h)

Problem Statement#

Given a node in a binary search tree where each node has a parent pointer, return the inorder successor of that node, or null if no successor exists. You do not have access to the root.

Constraints:

• Number of nodes is in [1, 10^4]
• -10^5 <= Node.val <= 10^5
• All values are unique
• Each node has a parent pointer (root's parent is null)

Input:  tree = [2,1,3], node = 1
Output: 2

Input:  tree = [5,3,6,2,4,null,null,1], node = 6
Output: null

Why This Problem Matters#

LeetCode 510 "Inorder Successor in BST II" is a Microsoft and Facebook favorite for senior engineers, especially in BST-heavy systems like database B-trees. It tests understanding of inorder traversal mechanics without the convenience of a global root pointer — a realistic constraint when dealing with iterators inside larger data structures.

The problem appears trivial at first ("just go right and then left") but the no-right-child case forces you to reason about ancestors. That nuance is exactly what separates juniors from seniors during onsite rounds.

The Core Insight#

There are two clean cases:

1. Node has a right child. The successor is the leftmost node of the right subtree. Walk right once, then keep walking left until null.
2. Node has no right child. Walk up via parent pointers until you find an ancestor for which the current node came from its left subtree. That ancestor is the successor. If you walk past the root, there is no successor.

Why does case 2 work? In an inorder traversal, you visit the left subtree, then the node, then the right subtree. After finishing a subtree from the right side, the next visit is the closest ancestor whose left subtree you just exited. Climb until that direction flips.

Visual Dry Run#

Tree [5,3,6,2,4,null,null,1], node = 4 (no right child).

Tree [2,1,3], node = 1 (no right child).

Solution (Optimal)#

class Solution:
    def inorderSuccessor(self, node):
        if node.right:
            curr = node.right
            while curr.left:
                curr = curr.left
            return curr
        curr = node
        while curr.parent and curr.parent.right is curr:
            curr = curr.parent
        return curr.parent

var inorderSuccessor = function(node) {
    if (node.right) {
        let curr = node.right;
        while (curr.left) curr = curr.left;
        return curr;
    }
    let curr = node;
    while (curr.parent && curr.parent.right === curr) {
        curr = curr.parent;
    }
    return curr.parent;
};

Time: O(h) — at most one traversal up or down the tree height. Space: O(1) — pointer-only iteration, no recursion or stack.

Common Mistakes#

• Going right and then right again instead of left when descending into the right subtree.
• In the climb-up case, climbing while curr is curr.parent.left (wrong direction).
• Forgetting to return null when climbing past the root.
• Treating the problem like LC 285 and walking from the root — you do not have root access here.
• Comparing values instead of pointers for the parent direction check.

Interview Tips#

• State the two cases clearly before coding. The structural distinction is the whole insight.
• Mention that without parent pointers, the problem becomes LC 285 and needs root access plus value comparison.
• Time complexity is O(h), which is O(log n) on a balanced BST and O(n) worst-case on a skewed tree.
• A clean iterative solution beats recursion here because there is no descent stack to maintain.

Follow-up Questions#

• Inorder predecessor: mirror the logic — left subtree's rightmost, or climb while curr is curr.parent.left. Hint: swap left and right.
• Successor without parent pointers (LC 285): descend from root tracking the lowest ancestor strictly greater than the target. Hint: BST search with bookkeeping.
• k-th successor: repeat k times or augment nodes with subtree sizes. Hint: order-statistics tree.
• Threaded BST: rewire nulls into successor pointers up front. Hint: Morris-style threading.
• Concurrent modifications: the tree changes under the iterator. Hint: snapshot or version stamps.

Key Takeaways#

• LeetCode 510 has two crisp cases: right-child-exists vs climb-via-parent.
• With parent pointers you do not need the root, mirroring real iterator implementations.
• Case 1: leftmost node of the right subtree is the successor.
• Case 2: climb until the current node is a left child of its parent.
• O(h) time and O(1) space — pointer-only, no stack.
• Returning null when climbing past root signals "no successor exists".
• Common at Microsoft, Facebook, Bloomberg, and any company with internal BST iterators.