Recursive O(N) per query

Node lca(Node root, Node p, Node q) {
  if (root == null || root == p || root == q) return root;
  Node left = lca(root.left, p, q);
  Node right = lca(root.right, p, q);
  if (left != null && right != null) return root;
  return left != null ? left : right;
}
Advertisement

BST LCA in O(H)

Node lca(Node root, int p, int q) {
  while (root != null) {
    if (p < root.val && q < root.val) root = root.left;
    else if (p > root.val && q > root.val) root = root.right;
    else return root;
  }
  return null;
}
Advertisement

Binary lifting O(log N) per query

Precompute 2^k-th ancestor for each node. Query: raise both to same depth, then jump upward together.

Euler tour + RMQ

Euler tour + depths. LCA = node with min depth between u and v's first occurrences. Uses sparse table for O(1) range min.