Lowest Common Ancestor

The Lowest Common Ancestor (LCA) of two nodes p and q in a tree is the deepest node that is an ancestor of both. It is a fundamental tree problem with applications in network routing, version control (merge-base), and compiler design.

Summary of Approaches

Approach Tree Type Time Space Notes
Path comparison Binary Tree O(n) O(n) Simple, two traversals
Single traversal Binary Tree O(n) O(h) One pass, recursive
BST traversal BST O(h) O(1) Exploits ordering
Parent pointers Any O(h) O(h) Iterative, if parent links exist

Where h = tree height (O(log n) for balanced, O(n) worst case).


Method 1: Path Comparison (Binary Tree)

Find path from root to each node, then compare the paths.

  1. Find path from root to n1, store in array path1
  2. Find path from root to n2, store in array path2
  3. Walk both arrays together — the last element where they agree is the LCA

Time: O(n) — two traversals + linear scan
Space: O(n) — two path arrays

def find_path(root, path, k):
    if root is None:
        return False
    path.append(root.val)
    if root.val == k:
        return True
    if find_path(root.left, path, k) or find_path(root.right, path, k):
        return True
    path.pop()
    return False

def lca_path(root, n1, n2):
    path1, path2 = [], []
    if not find_path(root, path1, n1) or not find_path(root, path2, n2):
        return None  # one or both nodes not present
    for i in range(min(len(path1), len(path2))):
        if path1[i] != path2[i]:
            return path1[i - 1]
    return path1[min(len(path1), len(path2)) - 1]

Method 2: Single Traversal (Binary Tree)

One recursive pass — O(n) time, O(h) space. This is the standard interview solution.

Intuition: If the current node is n1 or n2, it could be the LCA. Recurse into both subtrees. If both sides return non-null, the current node is the LCA (one target is in each subtree).

def lca(root, p, q):
    if root is None:
        return None
    if root.val == p or root.val == q:
        return root
    left  = lca(root.left,  p, q)
    right = lca(root.right, p, q)
    if left and right:
        return root         # p in one subtree, q in the other
    return left if left else right
Node* findLCA(Node* root, int n1, int n2) {
    if (root == nullptr) return nullptr;
    if (root->key == n1 || root->key == n2) return root;

    Node* left_lca  = findLCA(root->left,  n1, n2);
    Node* right_lca = findLCA(root->right, n1, n2);

    if (left_lca && right_lca) return root;
    return left_lca ? left_lca : right_lca;
}

Note: This assumes both nodes are present. If one is absent, it returns the present node as LCA rather than null. Pass boolean flags found1/found2 to handle this correctly.


Method 3: LCA in a Binary Search Tree (BST)

A BST's ordering lets us find the LCA in O(h) time without a full traversal.

Algorithm: Starting from the root:

  • Both p and q < root → LCA is in the left subtree
  • Both > root → LCA is in the right subtree
  • Otherwise → root is the LCA (paths to p and q diverge here)
def lca_bst(root, p, q):
    while root:
        if p < root.val and q < root.val:
            root = root.left
        elif p > root.val and q > root.val:
            root = root.right
        else:
            return root  # divergence point = LCA
    return None
func lcaBST(root *TreeNode, p, q int) *TreeNode {
    for root != nil {
        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 nil
}

Time: O(h) — O(log n) balanced, O(n) worst (skewed tree)
Space: O(1) iterative


Method 4: Using Parent Pointers

If nodes have parent pointers (common in OS process trees, DOM), use a depth-leveling approach similar to finding the intersection of two linked lists.

def lca_with_parents(p, q):
    def depth(node):
        d = 0
        while node.parent:
            node, d = node.parent, d + 1
        return d

    dp, dq = depth(p), depth(q)
    while dp > dq:
        p, dp = p.parent, dp - 1
    while dq > dp:
        q, dq = q.parent, dq - 1
    while p != q:
        p, q = p.parent, q.parent
    return p

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


Edge Cases (LeetCode #236)

Case Result
p is ancestor of q Returns p
q is ancestor of p Returns q
Neither is ancestor of the other Returns the split node
One node missing (Method 2) Returns the present node (use flags for strict correctness)