Inorder Successor in BST

Problem Given a node in a BST, find its inorder successor — the node with the smallest key greater than the given key. Solve both with and without a parent pointer.

Input / Output

• Input: BST root (or node with parent pointers), target node/key.
• Output: successor node or null (target is the maximum).

Constraints

• O(h) time, O(1) extra space expected (no full inorder traversal into a list).

Example

• BST [20,8,22,4,12,null,null,null,null,10,14], target 8 → 10; target 14 → 20.

Expected approach

• With parent pointers: if the node has a right subtree → leftmost node of it; else climb parents until coming up from a left child — that parent is the successor.
• Without parents: walk from the root with a candidate: if key < node.key, record node as candidate and go left; else go right; the last recorded candidate is the successor. Both O(h). The two-case analysis (right subtree vs ancestor) is the substance; predecessor is the mirror follow-on.