Inorder Successor in BST

Problem#

Given the root of a BST and a node p, return the in-order successor of p (the node with the smallest value greater than p.val), or null if none.

Examples#

For BST [2,1,3], p = 1 → 2.
For BST [5,3,6,2,4,null,null,1], p = 6 → null.

Constraints#

The number of nodes is in [1, 10^4]. All values unique.

Approach#

Walk down the BST. If a node’s value exceeds p->val, this is a potential successor; remember it and go left to find smaller candidates. Otherwise go right.

Solution#

class Solution {
public:
    TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) {
        TreeNode* succ = nullptr;
        while (root) {
            if (root->val > p->val) {
                succ = root;
                root = root->left;
            } else {
                root = root->right;
            }
        }
        return succ;
    }
};

func inorderSuccessor(root *TreeNode, p *TreeNode) *TreeNode {
    var succ *TreeNode
    for root != nil {
        if root.Val > p.Val {
            succ = root
            root = root.Left
        } else {
            root = root.Right
        }
    }
    return succ
}

from typing import Optional

class Solution:
    def inorderSuccessor(self, root: Optional[TreeNode], p: TreeNode) -> Optional[TreeNode]:
        succ: Optional[TreeNode] = None
        while root:
            if root.val > p.val:
                succ = root
                root = root.left
            else:
                root = root.right
        return succ

function inorderSuccessor(root, p) {
    let succ = null;
    while (root) {
        if (root.val > p.val) {
            succ = root;
            root = root.left;
        } else {
            root = root.right;
        }
    }
    return succ;
}

class Solution {
    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        TreeNode succ = null;
        while (root != null) {
            if (root.val > p.val) {
                succ = root;
                root = root.left;
            } else {
                root = root.right;
            }
        }
        return succ;
    }
}

function inorderSuccessor(root: TreeNode | null, p: TreeNode): TreeNode | null {
    let succ: TreeNode | null = null;
    while (root) {
        if (root.val > p.val) {
            succ = root;
            root = root.left;
        } else {
            root = root.right;
        }
    }
    return succ;
}

Editorial#

The successor is the smallest value greater than p. Going left after recording a candidate refines toward smaller-greater values; going right when node <= p skips entire smaller subtrees. The loop runs in O(h) without ever needing parent pointers.

Complexity#

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

Problem#

Examples#

Constraints#

Approach#

Solution#

Editorial#

Complexity#

Concept revision#

Keyboard shortcuts

Problem#

Examples#

Constraints#

Approach#

Solution#

Editorial#

Complexity#

Concept revision#

Related#