#235MediumTrees & BST

Lowest Common Ancestor of a BST

The tell: Two nodes in a BST, where ordering tells you which way to walk.

How you get there

1If both targets are smaller than the node, the answer is in the left subtree.
2If both are larger, it is in the right.
3Otherwise they straddle this node, so it is the lowest common ancestor.

Solution

Python

def lowest_common_ancestor(root, p, q):
    node = root
    while node:
        if p.val < node.val and q.val < node.val:
            node = node.left
        elif p.val > node.val and q.val > node.val:
            node = node.right
        else:
            return node          # the split point
    return None

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

What goes wrong

Using the general binary-tree LCA algorithm works but throws away the BST ordering and costs O(n).

Test yourself on DSA Next: Serialize and Deserialize Binary Tree →