Lowest Common Ancestor

    DSA · Advanced

    Definition

    The LCA of two nodes is the deepest node that has both as descendants.

    Frequent tree interview question and used in distance queries.

    Diagram

    35 ← 3 → 1LCA(5,1) = 3

    Flowchart

    If root is null or p or q, return rootSearch left and rightIf both found, root is LCAElse return the found side

    Example: LCA recursion

    t = (3, (5, None, None), (1, None, None))
def lca(n, p, q):
    if not n or n[0] in (p, q): return n
    l, r = lca(n[1], p, q), lca(n[2], p, q)
    return n if l and r else l or r
print(lca(t, 5, 1)[0])

    Output: 3

    Complexity

    O(n)

    Key points

    • In a BST, use values to go left/right
    • Binary lifting answers many queries fast

    Interview questions

    LCA in BST?

    Walk down: if both smaller go left, both larger go right, else current node.

    More DSA topics

    ArraysLinked ListStackQueue