gumgum's Garden🌼

LCA in a Binary Search Tree

If a node let's xx is the LCA of pp and qq then

p.val <= x.val <= q.val\begin{equation} \text{p.val <= x.val <= q.val} \end{equation}
def lowestCommonAncestor(root, p, q):
    # Bring the root in range
    if root.val < p.val and root.val < q.val:
        return lowestCommonAncestor(root.right, p, q)
    elif root.val > p.val and root.val > q.val:
        return lowestCommonAncestor(root.left, p, q)
    else:
        # This is LCA
        return root