Inorder Successor in BST II

medium tree bst binary tree

Problem

Each BST node has a parent pointer. Given a node, return its inorder successor (or null).

Inputnode = (val=2 in BST [1,2,3])

Output3

Two cases: right-subtree-leftmost, else climb until we're our parent's left child.

BST values (level-order)

node val

def inorder_successor(node):
    if not node: return None
    if node.right:
        cur = node.right
        while cur.left: cur = cur.left
        return cur
    while node.parent and node.parent.right is node:
        node = node.parent
    return node.parent

function inorderSuccessor(node) {
  if (!node) return null;
  if (node.right) {
    let cur = node.right;
    while (cur.left) cur = cur.left;
    return cur;
  }
  while (node.parent && node.parent.right === node) node = node.parent;
  return node.parent;
}

class Solution {
    public Node inorderSuccessor(Node node) {
        if (node == null) return null;
        if (node.right != null) {
            Node cur = node.right;
            while (cur.left != null) cur = cur.left;
            return cur;
        }
        while (node.parent != null && node.parent.right == node) node = node.parent;
        return node.parent;
    }
}

Node* inorderSuccessor(Node* node) {
    if (!node) return nullptr;
    if (node->right) {
        Node* cur = node->right;
        while (cur->left) cur = cur->left;
        return cur;
    }
    while (node->parent && node->parent->right == node) node = node->parent;
    return node->parent;
}

Explanation

The inorder successor is the next-larger value in the BST. Here each node carries a parent pointer, so we can find it by walking the tree directly, with no extra storage. There are two cases to handle.

Case 1: the node has a right child. Then the successor lives in that right subtree — specifically its leftmost node, because that is the smallest value larger than us. So we step into node.right and keep going left while cur.left exists.

Case 2: no right child. Then the successor is an ancestor. We climb upward through parent links, but only while we are a right child (meaning that parent is smaller than us, so it cannot be the answer). The moment we are a left child, that parent is the successor.

Example: in BST [6,2,8,1,4,7,9,null,null,3,5] take node 4. It has a right child 5, and 5 has no left child, so the successor is 5. For node 5 (no right child) we climb: 5 is the right child of 4, so go up; 4 is the left child of 6, so the successor is 6.

Because we only ever move down one path or up one path, the work is proportional to the tree height, giving O(h) time and O(1) space.

Time: O(h) Space: O(1)