Lowest Common Ancestor - Data Structures & Algorithms

The Lowest Common Ancestor (LCA) of two nodes p and q is the deepest node that is an ancestor of both. In simple language, it’s the first node where the paths from p and q to the root meet.

This is a classic interview problem because it tests recursion, tree understanding, and comes up as a building block in other problems (like finding the distance between two nodes).

What LCA Looks Like

LCA Examples

LCA(4, 5) = 2

╱╲

Both 4 and 5 are children of 2

LCA(4, 7) = 3

╱╲

4 is in left subtree, 7 is in right

LCA in a BST (The Easy Version)

In a BST, we can use the BST property to our advantage. If both p and q are smaller than the current node, the LCA is in the left subtree. If both are larger, it’s in the right subtree. If they split (one left, one right), the current node IS the LCA.

function lcaBST(root, p, q) {
  if (p.val < root.val && q.val < root.val)
    return lcaBST(root.left, p, q);   // both in left subtree
  if (p.val > root.val && q.val > root.val)
    return lcaBST(root.right, p, q);  // both in right subtree
  return root; // split point — this is the LCA
}

def lca_bst(root, p, q):
    if p.val < root.val and q.val < root.val:
        return lca_bst(root.left, p, q)   # both in left
    if p.val > root.val and q.val > root.val:
        return lca_bst(root.right, p, q)  # both in right
    return root  # split point — this is the LCA

TreeNode lcaBST(TreeNode root, TreeNode p, TreeNode q) {
    if (p.val < root.val && q.val < root.val)
        return lcaBST(root.left, p, q);   // both in left
    if (p.val > root.val && q.val > root.val)
        return lcaBST(root.right, p, q);  // both in right
    return root; // split point — this is the LCA
}

Time: O(h) — we follow a single path down. Space: O(h) for recursion (O(1) if we use a loop).

LCA in a General Binary Tree

Without the BST property, we can’t use value comparisons. Instead, we use a beautiful recursive approach:

If the current node is null, p, or q, return it.
Recurse on left and right subtrees.
If both sides return non-null, the current node is the LCA (p and q are on different sides).
If only one side returns non-null, that’s where both nodes are — return that side.

function lowestCommonAncestor(root, p, q) {
  if (!root || root === p || root === q) return root;
  const left = lowestCommonAncestor(root.left, p, q);
  const right = lowestCommonAncestor(root.right, p, q);
  if (left && right) return root;  // p and q on different sides
  return left || right;            // both on the same side
}

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  # p and q on different sides
    return left or right            # both on the same side

TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    if (root == null || root == p || root == q) return root;
    TreeNode left = lowestCommonAncestor(root.left, p, q);
    TreeNode right = lowestCommonAncestor(root.right, p, q);
    if (left != null && right != null) return root; // different sides
    return left != null ? left : right;              // same side
}

Time: O(n) — we might visit every node. Space: O(h) — recursion stack.

Walking Through the Logic

Let’s trace through finding LCA(4, 7) in our tree [3, 2, 7, 4, 5]:

Trace: LCA(4, 7)

At node 3: recurse left and right

At node 2: recurse left and right

At node 4: root === p, return 4

At node 5: not p or q, left=null, right=null → return null

Back at 2: left=4, right=null → return 4 (only left found)

At node 7: root === q, return 7

Back at 3: left=4, right=7 → both non-null, return 3 (LCA!)

Distance Between Two Nodes

A common follow-up: find the distance (number of edges) between two nodes. Once we have the LCA, the distance is:

distance(p, q) = depth(p) - depth(LCA) + depth(q) - depth(LCA)

Or equivalently: find the LCA, then calculate the distance from LCA to p and LCA to q, and add them.

function distFromNode(root, target, dist = 0) {
  if (!root) return -1;                   // not found
  if (root === target) return dist;
  const left = distFromNode(root.left, target, dist + 1);
  if (left !== -1) return left;           // found in left subtree
  return distFromNode(root.right, target, dist + 1);
}

function distBetween(root, p, q) {
  const lca = lowestCommonAncestor(root, p, q);
  return distFromNode(lca, p) + distFromNode(lca, q);
}

def dist_from_node(root, target, dist=0):
    if not root: return -1                # not found
    if root == target: return dist
    left = dist_from_node(root.left, target, dist + 1)
    if left != -1: return left            # found in left
    return dist_from_node(root.right, target, dist + 1)

def dist_between(root, p, q):
    lca = lowest_common_ancestor(root, p, q)
    return dist_from_node(lca, p) + dist_from_node(lca, q)

int distFromNode(TreeNode root, TreeNode target, int dist) {
    if (root == null) return -1;            // not found
    if (root == target) return dist;
    int left = distFromNode(root.left, target, dist + 1);
    if (left != -1) return left;            // found in left
    return distFromNode(root.right, target, dist + 1);
}

int distBetween(TreeNode root, TreeNode p, TreeNode q) {
    TreeNode lca = lowestCommonAncestor(root, p, q);
    return distFromNode(lca, p, 0) + distFromNode(lca, q, 0);
}

Time: O(n) for finding LCA + O(n) for distances = O(n) total.

Key Takeaways

LCA in a BST is easy — just follow the BST property until the paths to p and q split.
LCA in a general binary tree uses a clever recursive approach: recurse both sides, and if both return non-null, the current node is the answer.
The general LCA code is surprisingly short (about 5 lines) but the logic is deep. Make sure we can trace through it step by step.
Distance between two nodes = distance from LCA to p + distance from LCA to q.

In simple language, LCA is about finding where two paths from the root diverge. In a BST we can use value comparisons to walk down efficiently. In a general tree, we let recursion do the heavy lifting.