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.