Lowest Common Ancestor in Binary Tree in DSA Typescript

Mental Model

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

Analogy: Imagine two friends starting from different houses in a neighborhood and walking up the streets to find the first intersection where their paths cross. That intersection is their common meeting point.

      3
     / \
    5   1
   / \ / \
  6  2 0  8
    / \
   7   4

Nodes: 5 and 1
Goal: Find their lowest common ancestor

Dry Run Walkthrough

Input: Binary tree with nodes 3,5,1,6,2,0,8,7,4; find LCA of nodes 5 and 1

Goal: Find the lowest common ancestor node of 5 and 1 in the tree

Step 1: Start at root node 3, check if it matches 5 or 1

3 ↑
/ \
5  1
...

Why: We start from the root to explore both sides for the target nodes

Step 2: Recursively search left subtree for nodes 5 or 1

5 ↑
/ \
6  2
...

Why: Check if left subtree contains either target node

Step 3: Find node 5 matches target, return node 5 up

5 ↑

Why: Found one target node in left subtree

Step 4: Recursively search right subtree for nodes 5 or 1

1 ↑
/ \
0  8

Why: Check if right subtree contains either target node

Step 5: Find node 1 matches target, return node 1 up

1 ↑

Why: Found the other target node in right subtree

Step 6: At node 3, left returned 5 and right returned 1, so node 3 is LCA

3 ↑

Why: Both targets found in different subtrees, so current node is their lowest common ancestor

Result:

3
This is the lowest common ancestor of nodes 5 and 1

Annotated Code

DSA Typescript

class TreeNode {
  val: number;
  left: TreeNode | null;
  right: TreeNode | null;
  constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
    this.val = val === undefined ? 0 : val;
    this.left = left === undefined ? null : left;
    this.right = right === undefined ? null : right;
  }
}

function lowestCommonAncestor(root: TreeNode | null, p: TreeNode, q: TreeNode): TreeNode | null {
  if (root === null) return null;
  if (root === p || root === q) return root; // found one target

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

  if (left !== null && right !== null) return root; // targets found in both sides
  return left !== null ? left : right; // return non-null child or null
}

// Build tree nodes
const node7 = new TreeNode(7);
const node4 = new TreeNode(4);
const node2 = new TreeNode(2, node7, node4);
const node6 = new TreeNode(6);
const node5 = new TreeNode(5, node6, node2);
const node0 = new TreeNode(0);
const node8 = new TreeNode(8);
const node1 = new TreeNode(1, node0, node8);
const root = new TreeNode(3, node5, node1);

const lca = lowestCommonAncestor(root, node5, node1);
console.log(lca ? lca.val : 'null');

if (root === null) return null;

stop if reached empty subtree

if (root === p || root === q) return root; // found one target

return current node if it matches one target

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

search left subtree recursively

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

search right subtree recursively

if (left !== null && right !== null) return root; // targets found in both sides

if both sides found targets, current node is LCA

return left !== null ? left : right; // return non-null child or null

return whichever subtree found a target or null if none

Output

3

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 neither node found, or the found node if only one is present

DSA Typescript

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

Tree with only one node which is one of the targets

Returns that node as LCA

DSA Typescript

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

Both nodes are the same node

Returns that node as LCA immediately

DSA Typescript

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

When to Use This Pattern

When asked to find a shared ancestor or meeting point of two nodes in a tree, use the Lowest Common Ancestor pattern by recursively searching subtrees and identifying where paths split.

Common Mistakes

Mistake: Returning immediately after finding one target without checking the other subtree
Fix: Continue searching both subtrees to confirm if both targets exist and find the lowest common ancestor

Mistake: Confusing node values with node references when comparing nodes
Fix: Compare nodes by reference (identity), not just by value

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 of two nodes in a tree structure.

The key is to recursively search left and right subtrees and identify the node where both targets split.