Given a binary search tree and two nodes p and q, return their lowest common ancestor — the deepest node that has both as descendants (a node can be its own ancestor).
Exploiting the BST ordering — the LCA is the first node whose value sits between p and q — instead of a generic tree search.
In a general binary tree LCA needs a full search, but a BST's ordering collapses it to a single root-to-leaf walk. Compare the current node's value with p and q: if both are smaller, the answer lies entirely in the left subtree; if both are larger, go right; the moment they split — one on each side, or one equals the current node — you are standing on the lowest common ancestor, because this is the first node from the top where p and q diverge. No extra space beyond the walk, and it is O(h): O(log n) balanced, O(n) worst. Recognition signal: 'lowest common ancestor in a BST' (or any 'first point where two ordered search paths diverge') → descend using the BST comparison and stop at the split point. For a plain binary tree instead, use the postorder 'found-in-left / found-in-right' recursion.
LCA (or the split point of two search paths) in a BST → walk down comparing values, stop where the two targets fall on opposite sides of the current node.
Time O(h) · Space O(1) iterative