LCA of BST Solution

In a BST, you can determine which subtree contains each node by comparing values:

function lowestCommonAncestor(root, p, q):
    while root:
        if p.val < root.val and q.val < root.val:
            root = root.left
        else if p.val > root.val and q.val > root.val:
            root = root.right
        else:
            return root
    return null

If both values are smaller, both nodes are in the left subtree. If both are larger, both are in the right subtree. Otherwise, current node is the split point. That is the LCA.

Time: $O(h)$. Space: $O(1)$.

Compare this to the general binary tree LCA which is $O(n)$. The BST property lets us find LCA in $O(h)$ without checking both subtrees.