Lowest Common Ancestor
An interactive, step-by-step visualisation of Lowest Common Ancestor.
- Category
- Trees
- Time complexity
- O(n)
- Space complexity
- O(h)
Pseudocode
lca(t, p, q): if t has p or q in subtree: recurse both children if both children found one each: t is the LCA
Reference implementation
def lca(t, p, q):
if not t or t.v in (p, q): return t
l = lca(t.l, p, q); r = lca(t.r, p, q)
return t if l and r else (l or r)