Inorder Successor in BST II

Problem

Given a node in a BST (with parent pointer), find its inorder successor.

Key insight: Two cases — (1) node has right child: go right then all the way left; (2) no right child: go up until you come from a left child.

Solutions

// C++
Node* inorderSuccessor(Node* node) {
    if (node->right) {
        node = node->right;
        while (node->left) node = node->left;
        return node;
    }
    while (node->parent && node == node->parent->right)
        node = node->parent;
    return node->parent;
}

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

// JavaScript
function inorderSuccessor(node) {
    if (node.right) {
        node = node.right;
        while (node.left) node = node.left;
        return node;
    }
    while (node.parent && node === node.parent.right) node = node.parent;
    return node.parent;
}

# Python
def inorderSuccessor(node):
    if node.right:
        node = node.right
        while node.left:
            node = node.left
        return node
    while node.parent and node == node.parent.right:
        node = node.parent
    return node.parent

Complexity

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