Lowest Common Ancestor in a BST

Problem Given a binary search tree (BST) and two nodes p and q present in it, find their lowest common ancestor (LCA) — the deepest node that has both p and q as descendants (a node may be a descendant of itself). Solve it iteratively, without recursion.

Input / Output

• Input: the root of a BST and two node values p and q.
• Output: the LCA node of p and q.

Constraints

• Both p and q exist in the tree.
• The tree satisfies the BST ordering property (left subtree < node < right subtree).
• Solve in O(h) time where h is the tree height, using O(1) extra space.

Example

• In a BST rooted at 6 with children 2 and 8, LCA(2, 8) = 6; LCA(2, 4) = 2 (a node is its own ancestor).