5.23 Inorder Successor in BST

5.23.1 Problem Metadata

• Platform: LeetCode
• Problem ID: 285
• Difficulty: Medium
• URL: https://leetcode.com/problems/inorder-successor-in-bst/
• Tags:
• Techniques: Binary Search Tree, Tree

5.23.2 Description

Find the inorder successor of a given node in a BST.

5.23.3 Solution - BST Properties

5.23.3.1 Walkthrough

Exploit BST ordering:

• If p has a right subtree, successor is the leftmost node in p.right.
• Otherwise, walk down from root tracking the deepest ancestor whose value is greater than p.val (first left turn on the search path).

Iteratively compare p.val with root.val: when p.val < root.val, record root as a candidate successor and move left; otherwise move right to search larger values.

5.23.3.2 Analysis

• Time Complexity: O(h) where h is tree height
• Space Complexity: O(1)

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