Lowest Common Ancestor in Binary Tree in DSA Javascript

Mental Model

Find the closest shared parent node of two given nodes in a tree by checking where their paths meet.

Analogy: Imagine a family tree where you want to find the closest common grandparent of two cousins by tracing their parents upwards until you find the same person.

      1
     / \
    2   3
   / \   \
  4   5   6

Dry Run Walkthrough

Input: Binary tree: 1->2->4, 2->5, 1->3->6; find LCA of nodes 4 and 5

Goal: Find the lowest node that is an ancestor of both 4 and 5

Step 1: Start at root node 1, check left and right subtrees for nodes 4 and 5

At node 1: searching left subtree -> 2, right subtree -> 3

Why: We need to explore both sides to find nodes 4 and 5

Step 2: At node 2, check left child 4 and right child 5

At node 2: left child 4 found, right child 5 found

Why: Both nodes found in different subtrees of 2, so 2 is common ancestor

Step 3: Return node 2 as LCA since both nodes found in its subtrees

LCA found: node 2

Why: Lowest node with both nodes in its subtrees is the answer

Result:

2

Annotated Code

DSA Javascript

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

function lowestCommonAncestor(root, p, q) {
  if (root === null) return null;
  if (root === p || root === q) return root;

  const left = lowestCommonAncestor(root.left, p, q);
  const right = lowestCommonAncestor(root.right, p, q);

  if (left !== null && right !== null) return root;
  return left !== null ? left : right;
}

// Build tree
const root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(5);
root.right.right = new TreeNode(6);

const p = root.left.left;  // Node 4
const q = root.left.right; // Node 5

const lca = lowestCommonAncestor(root, p, q);
console.log(lca.val);

if (root === null) return null;

stop if reached empty subtree

if (root === p || root === q) return root;

return current node if it matches one of the targets

const left = lowestCommonAncestor(root.left, p, q);

search left subtree for targets

const right = lowestCommonAncestor(root.right, p, q);

search right subtree for targets

if (left !== null && right !== null) return root;

if targets found in both subtrees, current node is LCA

return left !== null ? left : right;

otherwise return non-null subtree result

Output

2

Complexity Analysis

Time: O(n) because we visit each node once in the worst case

Space: O(h) where h is tree height due to recursion stack

vs Alternative: Compared to storing paths for both nodes and comparing, this approach uses less space and is simpler

Edge Cases

One or both nodes not present in tree

Function returns null if either node is missing

DSA Javascript

if (root === null) return null;

One node is ancestor of the other

Ancestor node is returned as LCA

DSA Javascript

if (root === p || root === q) return root;

Tree with only one node which is both p and q

That node is returned as LCA

DSA Javascript

if (root === p || root === q) return root;

When to Use This Pattern

When asked to find the closest shared parent of two nodes in a tree, use the Lowest Common Ancestor pattern because it efficiently finds the meeting point of their paths.

Common Mistakes

Mistake: Returning immediately after finding one node without checking the other subtree
Fix: Always search both left and right subtrees before deciding the LCA

Mistake: Not handling the case when one node is ancestor of the other
Fix: Return current node if it matches either target node

Summary

Finds the lowest node that is an ancestor of two given nodes in a binary tree.

Use when you need to find the closest shared parent node of two nodes in a tree.

The key insight is that if one node is found in the left subtree and the other in the right, the current node is their lowest common ancestor.