Lowest Common Ancestor Explained: Algorithms, Code & Applications

Imagine you're building a family tree app. You've got thousands of relatives mapped out, and a user asks: "Who is the closest shared ancestor of my great-grandmother and my cousin twice removed?" That's not just a genealogy puzzle—it's a classic computer science problem known as finding the lowest common ancestor (LCA). The same concept that powers your family tree app also underpins version control systems like Git, helps biologists trace the origins of life, and shows up in countless coding interviews.

In this guide, I'll walk you through everything you need to know about the lowest common ancestor: what it is, how to find it efficiently in a binary tree, and why the same idea appears in fields as diverse as evolutionary biology and distributed systems. By the end, you'll have multiple algorithms in your toolkit, complete with Python, C++, Java, and JavaScript implementations.

---

What is the Lowest Common Ancestor in a Binary Tree?

Formal Definition and Core Concepts

Let's start with the formal definition. Given a tree and two nodes n1 and n2, the LCA in binary tree is the deepest node that has both n1 and n2 as descendants. Here's the catch that trips up many beginners: a node is considered a descendant of itself. So if you're looking for the LCA of a node and its parent, the parent is the answer.

Consider this simple tree:

  1
 / \
2   3

The LCA of nodes 2 and 3 is node 1. The LCA of nodes 1 and 2 is also node 1, because node 1 is an ancestor of itself. This self-descendant rule isn't just a technicality—it's essential for the recursive algorithms we'll explore shortly.

To find the LCA, we typically rely on tree traversal techniques, particularly depth-first search (DFS). The idea is to explore the tree systematically, tracking which target nodes we've found in each subtree.

LCA vs. Other Ancestor Concepts

Before diving into algorithms, let's clear up some terminology that often causes confusion:

There's also the concept of parent pointers—each node stores a reference to its parent. This makes finding ancestors trivial (just walk up the chain), but it requires extra memory and isn't always available.

---

Core Algorithms for Finding the Lowest Common Ancestor

The Recursive Single Traversal Approach

This is the algorithm I reach for first in interviews. It's elegant, efficient, and surprisingly concise. The lowest common ancestor algorithm works like this:

1. If the current node is null or matches either target node, return it.
2. Recursively search the left and right subtrees.
3. If both recursive calls return non-null values, the current node is the LCA.
4. If only one returns non-null, propagate that result upward.

Here's the implementation in Python:

class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

def lowest_common_ancestor(root, p, q):
    """
    Find the LCA of nodes p and q in a binary tree.
    
    Args:
        root: The root of the binary tree
        p, q: The two target nodes
    
    Returns:
        The LCA node, or None if not found
    """
    # Base case: null node or found a target
    if root is None or root == p or root == q:
        return root
    
    # Recursively search left and right subtrees
    left_result = lowest_common_ancestor(root.left, p, q)
    right_result = lowest_common_ancestor(root.right, p, q)
    
    # If both subtrees return non-null, current node is the LCA
    if left_result and right_result:
        return root
    
    # Otherwise, return whichever side found something
    return left_result if left_result else right_result

The time complexity is O(n), where n is the number of nodes, because we potentially visit every node once. The space complexity is O(h), where h is the tree height, due to the recursion stack. In a balanced tree, that's O(log n); in a skewed tree, it degrades to O(n).

I've used this exact implementation in production code for a document hierarchy system. The elegance isn't just aesthetic—it's efficient and handles edge cases gracefully.

Iterative Approach with Parent Pointers

Sometimes recursion isn't ideal—perhaps the tree is deeply nested and you're worried about stack overflow. An alternative approach uses a hash map to store parent pointers.

The strategy:

1. Perform a BFS or DFS to populate a parent map for every node.
2. Trace the path from node p to the root, storing visited nodes in a set.
3. Walk up from node q, checking if each ancestor is in the set. The first match is the LCA.

Here's a C++ implementation:

#include <unordered_map>
#include <unordered_set>
#include <queue>

class Node {
public:
    int data;
    Node* left;
    Node* right;
    Node(int val) : data(val), left(nullptr), right(nullptr) {}
};

Node* findLCA(Node* root, Node* p, Node* q) {
    if (!root) return nullptr;
    
    // Map to store parent pointers
    std::unordered_map<Node*, Node*> parent;
    parent[root] = nullptr;
    
    // BFS to populate parent map
    std::queue<Node*> queue;
    queue.push(root);
    
    while (!queue.empty() && (parent.find(p) == parent.end() || 
                              parent.find(q) == parent.end())) {
        Node* current = queue.front();
        queue.pop();
        
        if (current->left) {
            parent[current->left] = current;
            queue.push(current->left);
        }
        if (current->right) {
            parent[current->right] = current;
            queue.push(current->right);
        }
    }
    
    // Trace path from p to root
    std::unordered_set<Node*> ancestors;
    while (p) {
        ancestors.insert(p);
        p = parent[p];
    }
    
    // Walk up from q, find first common ancestor
    while (q) {
        if (ancestors.find(q) != ancestors.end()) {
            return q;
        }
        q = parent[q];
    }
    
    return nullptr;
}

The trade-off is clear: we use O(n) extra space for the parent map, but we avoid recursion entirely. This approach shines when you're working with trees that might be too deep for safe recursion.

Optimized Approach for Binary Search Trees (BST)

If you're working with a binary search tree, you can do much better than O(n). The BST property—left child < parent < right child—lets us make a decision at each node about which subtree to search.

The algorithm:

1. Start at the root.
2. If both nodes are smaller than the current node, go left.
3. If both are larger, go right.
4. Otherwise, the current node is the LCA.

Here's a JavaScript implementation:

class TreeNode {
    constructor(val) {
        this.val = val;
        this.left = null;
        this.right = null;
    }
}

function lowestCommonAncestorBST(root, p, q) {
    let current = root;
    
    while (current) {
        // Both nodes are in the left subtree
        if (p.val < current.val && q.val < current.val) {
            current = current.left;
        }
        // Both nodes are in the right subtree
        else if (p.val > current.val && q.val > current.val) {
            current = current.right;
        }
        // We've found the split point—this is the LCA
        else {
            return current;
        }
    }
    
    return null;
}

The time complexity drops to O(h), where h is the tree height. In a balanced BST, that's O(log n)—a significant improvement over the general binary tree approach. I've seen this optimization make a real difference in systems that process millions of queries against a static BST.

---

Advanced Techniques and Real-World Applications

Binary Lifting and Euler Tour for Efficient Queries

What if you need to answer thousands of LCA queries on the same tree? Running the O(n) algorithm each time would be painfully slow. This is where binary lifting comes in.

Binary lifting is a dynamic programming technique that precomputes the 2^k-th ancestor for every node. After O(n log n) preprocessing, each LCA query takes just O(log n) time.

The core idea:

1. Build a table up[node][k] that stores the 2^k-th ancestor of each node.
2. To find the LCA of two nodes, first bring them to the same depth, then jump upward in decreasing powers of two.

Here's a pseudocode sketch:

for each node:
    up[node][0] = parent[node]
    for k = 1 to LOG:
        up[node][k] = up[up[node][k-1]][k-1]

def lca(u, v):
    if depth[u] < depth[v]:
        swap(u, v)
    
    # Bring u up to v's depth
    for k = LOG down to 0:
        if depth[u] - 2^k >= depth[v]:
            u = up[u][k]
    
    if u == v:
        return u
    
    # Jump both up together
    for k = LOG down to 0:
        if up[u][k] != up[v][k]:
            u = up[u][k]
            v = up[v][k]
    
    return up[u][0]

An alternative approach uses the Euler tour technique combined with a Range Minimum Query (RMQ) data structure. The Euler tour flattens the tree into an array, and the LCA of two nodes corresponds to the node with minimum depth in the range between their first occurrences.

Both techniques have their place. Binary lifting is simpler to implement and works well for most use cases. The Euler tour + RMQ approach can be faster for certain query patterns but requires more sophisticated data structures.

LCA in Complex Structures: N-ary Trees and DAGs

Binary trees are just the beginning. The LCA problem extends naturally to N-ary trees (where nodes can have any number of children). The recursive approach we discussed earlier works with minimal modification—instead of checking left and right children, you iterate through all children.

But what about Directed Acyclic Graphs (DAGs)? This is where things get genuinely tricky. In a DAG, multiple paths can exist between two nodes, which means the concept of "ancestor" becomes ambiguous. A node might be reachable from multiple parents, and the "lowest" common ancestor isn't always well-defined.

Can the lowest common ancestor be found in a graph? The short answer is: it depends on the graph structure. For trees, the answer is a clean yes. For DAGs, the problem becomes significantly harder and often requires more sophisticated algorithms. In general DAGs, you might need to find all common ancestors and then determine which ones are "lowest" based on the partial order defined by reachability.

From Code to Biology: The Surprising Parallel of LUCA

Here's where the story takes an unexpected turn. The same concept that helps you solve LeetCode problems also appears in evolutionary biology—with a twist.

In biology, LUCA stands for the Last Universal Common Ancestor. This is the most recent population of organisms from which all life on Earth descends. It's not the first life form, but rather the most recent common ancestor of all currently living organisms.

The parallel is striking. In a phylogenetic tree (a tree showing evolutionary relationships), the LCA of two species is the point where their evolutionary lineages diverged. LUCA is simply the LCA of all life on Earth—the root of the tree of life.

So, who was the last common ancestor? Scientists estimate that LUCA lived about 3.5 to 3.8 billion years ago [需核实]. It was likely a single-celled organism, possibly similar to modern bacteria or archaea, that lived near hydrothermal vents in the deep ocean.

And yes, in a very real sense, we are all technically cousins. Every living thing on Earth—from bacteria to blue whales to you—shares a common ancestor. The algorithmic concept of LCA and the biological concept of LUCA are two sides of the same coin: the universal principle of common ancestry.

---

Mastering LCA for Coding Interviews (LeetCode & More)

Common LeetCode Problems and Solution Strategies

If you're preparing for coding interviews, you'll encounter LCA problems frequently. Here are the most common ones:

Common pitfalls I've seen in interviews:

• Forgetting that a node is a descendant of itself
• Not handling the case where one node is an ancestor of the other
• Failing to explain time and space complexity clearly

Comparing Different Solutions: Which One to Choose?

Here's a comparison table I wish I'd had when I was preparing for interviews:

---

Frequently Asked Questions

What is the time complexity of the lowest common ancestor algorithm?

The time complexity depends on the algorithm you choose:

How to implement lowest common ancestor in Python?

Here's the cleanest Python implementation using the recursive approach:

def lowest_common_ancestor(root, p, q):
    if not root or root == p or root == q:
        return root
    
    left = lowest_common_ancestor(root.left, p, q)
    right = lowest_common_ancestor(root.right, p, q)
    
    if left and right:
        return root
    
    return left or right

This is the solution I'd give in an interview. It's concise, correct, and easy to explain.

What is the difference between lowest common ancestor and highest common ancestor?

The highest common ancestor of two nodes is simply the root of the tree (assuming both nodes are in the same tree). The lowest common ancestor is the deepest node that is an ancestor of both nodes. In a tree with root 1, left child 2, and right child 3, both the highest and lowest common ancestors of 2 and 3 are node 1. But in a deeper tree, they'd be different nodes.

What is Fuca and LUCA?

LUCA stands for Last Universal Common Ancestor—the most recent population of organisms from which all life on Earth descends. "Fuca" is almost certainly a typo or mishearing of LUCA. There's no widely recognized biological concept called "Fuca" in this context.

---

Conclusion

We've covered a lot of ground, from the basic definition of the lowest common ancestor in binary trees to advanced techniques like binary lifting, and even a detour into evolutionary biology. The recursive single-traversal approach is the foundation—master it first, then build from there.

The parallel between the algorithmic LCA and the biological LUCA is more than just a fun fact. It highlights how a single abstract concept can manifest in wildly different domains. Whether you're tracing family trees, debugging distributed systems, or reconstructing the tree of life, the principle is the same: find the deepest point where two paths converge.

My advice? Practice implementing these algorithms by hand. Write the recursive approach from memory. Then modify it for BSTs. Then try the iterative version. The more comfortable you are with the variations, the better prepared you'll be for whatever interview question comes your way.

Ready to test your skills? Head over to LeetCode and try solving problem #236 (Lowest Common Ancestor of a Binary Tree) using the recursive approach. Then, challenge yourself with the BST variant (#235). Share your solution or ask questions in the comments below!