Lowest Common Ancestor (LCA)

March 2026 · 8 min read

The Problem

Given a binary tree and two nodes p and q, find their Lowest Common Ancestor, the deepest node that is an ancestor of both. Every pair of nodes in a tree has exactly one LCA (the root is always a common ancestor, but we want the lowest one).

LCA appears everywhere: in version control (finding the common commit of two branches), in computational biology (finding the common ancestor of two species in a phylogenetic tree), and as a building block for computing distances between nodes.

Distance formula: The distance between two nodes p and q equals depth(p) + depth(q) - 2 * depth(LCA(p, q)). This is how LCA becomes essential for path-based queries.

Approach 1: BST-Specific LCA: O(h)

If the tree is a BST, the ordering property gives us a shortcut. Starting from the root:

• If both p and q are less than the current node → the LCA must be in the left subtree.
• If both are greater than the current node → the LCA must be in the right subtree.
• Otherwise, the current node is the split point where p and q diverge to different subtrees, this node is the LCA.

Why the Split Point Works

In a BST, once two values go to different subtrees, they can never come back together. If p goes left and q goes right at some node, that node is the last shared ancestor. Any node deeper will only contain one of them.

// Recursive
TreeNode* lcaBST(TreeNode* root, int p, int q) {
    if (p < root->val && q < root->val)
        return lcaBST(root->left, p, q);   // both left
    if (p > root->val && q > root->val)
        return lcaBST(root->right, p, q);  // both right
    return root;  // split point = LCA
}

// Iterative (O(1) space)
TreeNode* lcaBSTIterative(TreeNode* root, int p, int q) {
    while (root) {
        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 nullptr;
}

Time: O(h), we descend at most one root-to-leaf path.
Space: O(h) recursive, or O(1) iterative.

Approach 2: General Tree LCA: O(n)

For a general binary tree (not necessarily a BST), we can't use ordering. Instead, we use a single DFS pass with a clever observation:

At each node, we ask: "Is p or q in my left subtree? Is p or q in my right subtree?" There are three cases:

• Both found in different subtrees → I am the LCA (they split here).
• Both found in the same subtree → the LCA is deeper in that subtree.
• I am p or q myself → I am the LCA (the other node must be in my subtree).

TreeNode* lcaGeneral(TreeNode* root, TreeNode* p, TreeNode* q) {
    if (!root || root == p || root == q)
        return root;  // base: null or found one of our targets

    auto* left  = lcaGeneral(root->left, p, q);
    auto* right = lcaGeneral(root->right, p, q);

    if (left && right) return root;  // p and q are in different subtrees
    return left ? left : right;       // both in the same subtree
}

Why Does This Work?

The recursion returns a non-null result only when it finds p or q (or the LCA itself). If both left and right return non-null at some node, that means p and q are on opposite sides, making that node the LCA. If only one side returns non-null, both targets are in that subtree and the answer propagates upward.

Edge case: If p is an ancestor of q, then when we encounter p, we return it immediately. The recursion into p's subtree will find q, but we never need the result because p is already the answer.

Time: O(n), we may visit every node in the worst case.
Space: O(h) for the recursion stack.

Comparison

Advanced: LCA with Preprocessing

For repeated LCA queries on the same tree, you can preprocess to answer each query in O(1) or O(log n):

• Binary Lifting: Preprocess in O(n log n). Each query in O(log n). Store 2^k-th ancestors for each node.
• Euler Tour + Range Minimum Query: Preprocess in O(n). Each query in O(1). Reduce LCA to RMQ on the Euler tour array.
• Tarjan's Offline LCA: O(n + q) for all queries at once using Union-Find. Processes all queries in one DFS pass.

These are beyond the scope of this post but worth knowing about for competitive programming and systems design interviews.