Tree Algorithms

Lowest Common Ancestor

What is the Lowest Common Ancestor?

The Lowest Common Ancestor of two nodes A and B is the deepest node in the tree that has both A and B as descendants (a node counts as its own descendant, so LCA(A, A) is just A). It's "lowest" in the sense of being as far from the root as possible while still being an ancestor of both — the point where the paths from A and B up to the root first merge.

How Does It Work?

On a general binary tree (no ordering guarantee), finding the LCA needs to search the whole tree: recursively check the left and right subtrees for A and B. If a node's left subtree contains one of them and its right subtree contains the other, that node is the split point — the LCA. If only one subtree contains either of them, the LCA must be further down inside that subtree.

A Binary Search Tree's ordering turns this into something far cheaper. Starting at the root and comparing both values against the current node: if both A and B are smaller, the LCA must be somewhere in the left subtree (skip the right entirely). If both are larger, it must be in the right subtree. The moment they're no longer both on the same side — one is smaller (or equal) and the other is larger (or equal) — the paths to A and B have just diverged, and the current node is the LCA. No backtracking, no exploring the "wrong" subtree at all.

LCA(1, 6) — paths to 1 and 6 split apart at node 3
831016
Node A / Node BLowest Common Ancestor

Algorithm Steps (BST)

  1. Start at the root
  2. Compare both target values against the current node's value:
    • If both are smaller, move to the left child
    • If both are larger, move to the right child
    • Otherwise (one is smaller-or-equal and the other is larger-or-equal), the current node is the LCA — stop
  3. Repeat until the split point is found

Time Complexity

  • Best/Average Case: Roughly balanced tree → O(log n).
  • Worst Case: Degenerate/skewed tree → O(n).

Time Complexity Analysis

Advertisement

LCA queries show up any time a "closest shared point" needs to be found across two positions in a hierarchy: git's merge-base command (the common ancestor commit two branches diverged from), routing decisions in network topology trees, and evolutionary/phylogenetic trees (the most recent common ancestor of two species). When the same tree needs many repeated LCA queries, the answers are often precomputed into an O(1)-per-query structure using techniques built on top of range-minimum queries.

Daily DSA Challenge by Scale Engineer

Pick two nodes and watch their paths converge at the Lowest Common Ancestor

Tree is empty
No tree yet — insert a value or generate a random tree
Internal nodeLeaf nodeRootDescent pathNode A / Node BLowest Common AncestorEliminated subtree

Test Your Knowledge before moving forward!

Lowest Common Ancestor Quiz

How it works:

  • +1 point for each correct answer
  • 0 points for wrong answers
  • -0.5 point penalty for viewing explanations
  • Earn stars based on your final score (max 5 stars)

Lowest Common Ancestor Implementation

// Binary tree node
class TreeNode {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}

// BST-specific LCA: uses ordering to avoid exploring the "wrong" subtree
function lowestCommonAncestorBST(root, p, q) {
  let node = root;
  while (node) {
    if (p < node.value && q < node.value) {
      node = node.left;
    } else if (p > node.value && q > node.value) {
      node = node.right;
    } else {
      return node; // paths diverge here — this is the LCA
    }
  }
  return null; // one or both values aren't in the tree
}

// General binary tree LCA (no ordering assumed): search both subtrees
function lowestCommonAncestor(root, p, q) {
  if (root === null || root.value === p || root.value === 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 found in different subtrees
  return left || right;           // both in the same subtree, or not found
}

// Usage example
let root = null;
[8, 3, 10, 1, 6, 14].forEach((v) => {
  root = insert(root, v); // see BST Insertion for insert
});

lowestCommonAncestorBST(root, 1, 6).value;  // 3
lowestCommonAncestor(root, 1, 6).value;     // 3 (also works without BST ordering)

Done With the Learning

Mark Lowest Common Ancestor as done and view it on your dashboard

Explore Other Tree Topics

Tree Diameter

Tree Isomorphism

Serialize/Deserialize

BST Searching

BST Insertion

AVL Balancing

In-order Traversal

Structure & Properties