Solving Lowest Common Ancestor in JavaScript: Step-by-Step Guide

Introduction to Lowest Common Ancestor

The Lowest Common Ancestor (LCA) is a fundamental concept in tree data structures and graph theory. Given two nodes in a tree, the LCA is the deepest node that has both nodes as descendants. Understanding how to compute the LCA efficiently is essential for solving a wide range of algorithmic problems, from file system path resolution to computational biology and version control systems.

In this tutorial, we will explore what the Lowest Common Ancestor is, why it matters, how to implement it in JavaScript using multiple approaches, and the best practices you should follow when working with tree-based algorithms.

What Is the Lowest Common Ancestor?

A tree is a hierarchical data structure consisting of nodes connected by edges, with a single root node at the top. Each node has at most one parent, and there are no cycles. In such a structure, the Lowest Common Ancestor of two nodes p and q is defined as the lowest node in the tree that has both p and q as descendants (where a node can be a descendant of itself).

Consider the following binary tree:

In this example:

The LCA of nodes 5 and 1 is 3.
The LCA of nodes 5 and 4 is 5, because a node is considered a descendant of itself.
The LCA of nodes 6 and 4 is 5.

Why the LCA Matters

The LCA problem appears in many real-world scenarios and technical applications:

File systems: Finding the common parent directory of two files.
Version control: Git uses LCA to determine the merge base of two branches.
Computational biology: Phylogenetic trees use LCA to find the most recent common ancestor of two species.
Routing and networks: Determining the common upstream node between two endpoints.
Range queries: LCA is a building block for more complex algorithms like range minimum queries.

Because trees can be very large, the efficiency of LCA computation directly impacts the performance of these systems. A naive approach may work for small trees, but production-grade applications require optimized solutions.

Representing a Tree in JavaScript

Before we solve the LCA problem, we need a way to represent a binary tree in JavaScript. The most common approach is to use a class-based node structure:

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

// Build the example tree
const root = new TreeNode(3,
  new TreeNode(5,
    new TreeNode(6),
    new TreeNode(2,
      new TreeNode(7),
      new TreeNode(4)
    )
  ),
  new TreeNode(1,
    new TreeNode(0),
    new TreeNode(8)
  )
);

Each TreeNode holds a value and references to its left and right children. With this structure in place, we can implement several LCA algorithms.

Approach 1: Recursive Depth-First Search

The most intuitive way to find the LCA in a binary tree is to use recursion. The idea is simple: traverse the tree from the root downward. At each node, check whether the current node is one of the target nodes, or whether the targets exist in its left or right subtrees. The node where both targets are found in different subtrees (or where the current node itself is one of the targets) is the LCA.

Implementation

function lowestCommonAncestor(root, p, q) {
  // Base case: if root is null, return null
  if (root === null) {
    return null;
  }

  // If the current node is one of p or q, return it
  if (root === p || root === q) {
    return root;
  }

  // Recurse on left and right subtrees
  const left = lowestCommonAncestor(root.left, p, q);
  const right = lowestCommonAncestor(root.right, p, q);

  // If both sides returned a non-null value, current node is the LCA
  if (left !== null && right !== null) {
    return root;
  }

  // Otherwise, return whichever side found a target
  return left !== null ? left : right;
}

How It Works

The recursion works by bubbling up information from the leaves to the root. When a node finds that both its left and right recursive calls returned a non-null result, it means one target was found in each subtree, so this node must be the LCA. If only one side returns a non-null value, that value is propagated upward. This approach assumes that both p and q exist in the tree.

Time and Space Complexity

Time complexity: O(n), where n is the number of nodes, because in the worst case we visit every node.
Space complexity: O(h), where h is the height of the tree, due to the recursion stack. In a balanced tree, this is O(log n); in a skewed tree, it is O(n).

Approach 2: Storing Parent Pointers

If the tree nodes include a reference to their parent, we can solve the LCA problem without recursion. The strategy is to collect all ancestors of p by walking up to the root, then walk up from q until we encounter a node that is also an ancestor of p.

Implementation

class TreeNodeWithParent {
  constructor(val, left = null, right = null, parent = null) {
    this.val = val;
    this.left = left;
    this.right = right;
    this.parent = parent;
  }
}

function lowestCommonAncestorWithParent(p, q) {
  const ancestors = new Set();

  // Collect all ancestors of p (including p itself)
  let current = p;
  while (current !== null) {
    ancestors.add(current);
    current = current.parent;
  }

  // Walk up from q until we find a common ancestor
  current = q;
  while (current !== null) {
    if (ancestors.has(current)) {
      return current;
    }
    current = current.parent;
  }

  return null; // No common ancestor found
}

Complexity Analysis

Time complexity: O(h), since we traverse from each node up to the root.
Space complexity: O(h), for storing the ancestors of p in the set.

This approach is particularly useful when the tree is immutable and nodes already store parent references, such as in DOM trees or certain database indexes.

Approach 3: Binary Search Tree Optimization

If the tree is a Binary Search Tree (BST), we can exploit the BST property to find the LCA more efficiently. In a BST, for any node, all values in the left subtree are smaller and all values in the right subtree are larger. Therefore, we can decide which direction to traverse based on the values of p and q.

Implementation

function lowestCommonAncestorBST(root, p, q) {
  let current = root;

  while (current !== null) {
    // If both p and q are smaller, LCA is in the left subtree
    if (p.val < current.val && q.val < current.val) {
      current = current.left;
    }
    // If both p and q are larger, LCA is in the right subtree
    else if (p.val > current.val && q.val > current.val) {
      current = current.right;
    }
    // Otherwise, current is the split point, hence the LCA
    else {
      return current;
    }
  }

  return null;
}

Complexity Analysis

Time complexity: O(h), where h is the height of the tree. In a balanced BST, this is O(log n).
Space complexity: O(1), since we use an iterative approach with no extra data structures.

This is the most efficient approach when the BST property is guaranteed, making it ideal for database lookups and search-based applications.

Approach 4: Handling Cases Where Nodes May Not Exist

The recursive approach in Approach 1 assumes both p and q exist in the tree. In real-world scenarios, this assumption may not hold. We can modify the algorithm to track whether both nodes were actually found.

function lowestCommonAncestorSafe(root, p, q) {
  let result = null;

  function helper(node) {
    if (node === null) return false;

    const mid = (node === p || node === q);
    const left = helper(node.left);
    const right = helper(node.right);

    // If two of the three flags are true, this node is the LCA
    if (mid + left + right >= 2) {
      result = node;
    }

    // Return true if this subtree contains p or q
    return mid || left || right;
  }

  helper(root);
  return result;
}

This version sets result only when at least two of the three conditions (current node is a target, left subtree contains a target, right subtree contains a target) are true. If only one target exists in the tree, result remains null, correctly indicating that no valid LCA exists.

Best Practices

Choose the right approach for your tree type: Use the BST optimization when applicable, as it offers the best performance.
Validate inputs: Always check whether root, p, and q are valid before processing.
Handle missing nodes: If there is any chance that p or q might not exist, use the safe variant that tracks whether both nodes were found.
Avoid deep recursion for large trees: JavaScript has a call stack limit. For very deep trees, consider converting the recursive solution to an iterative one using an explicit stack.
Cache results for repeated queries: If you need to answer many LCA queries on the same tree, consider preprocessing with techniques like Sparse Table or Euler tour with RMQ for O(1) queries after O(n log n) preprocessing.
Write tests: Test edge cases such as when p equals q, when one node is the ancestor of the other, and when nodes are at opposite ends of the tree.

Testing the Implementation

Here is a simple test suite to verify the recursive implementation against the example tree:

function testLCA() {
  const node5 = root.left;
  const node1 = root.right;
  const node6 = root.left.left;
  const node4 = root.left.right.right;

  console.log(
    lowestCommonAncestor(root, node5, node1).val === 3
      ? "Test 1 passed" : "Test 1 failed"
  );

  console.log(
    lowestCommonAncestor(root, node5, node4).val === 5
      ? "Test 2 passed" : "Test 2 failed"
  );

  console.log(
    lowestCommonAncestor(root, node6, node4).val === 5
      ? "Test 3 passed" : "Test 3 failed"
  );
}

testLCA();

Running these tests should confirm that all three cases produce the expected results, giving you confidence that the implementation is correct.

Conclusion

The Lowest Common Ancestor is a versatile and widely applicable algorithm that every JavaScript developer working with tree structures should understand. Whether you are working with a general binary tree, a binary search tree, or a tree with parent pointers, there is an efficient approach tailored to your needs. By starting with the recursive solution and progressing to optimized variants, you can handle everything from simple interview problems to complex production scenarios. Remember to validate your inputs, account for missing nodes, and choose the most efficient algorithm based on the properties of your tree. With these tools in hand, you are well-equipped to solve LCA problems confidently and correctly in any JavaScript application.