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.

Practice

1. What is the Lowest Common Ancestor (LCA) in a binary tree?

easy

A. The root node of the binary tree

B. The lowest node that has both given nodes as descendants

C. The node with the highest value in the tree

D. The leaf node closest to the root

Solution

1. Step 1: Understand the definition of LCA

   The Lowest Common Ancestor is the lowest node in the tree that has both given nodes as descendants (a node can be a descendant of itself).

2. Step 2: Differentiate from other nodes

   It is not necessarily the root or the highest value node, but the shared ancestor closest to the two nodes.

3. Final Answer:

   The lowest node that has both given nodes as descendants -> Option B

4. Quick Check:

   LCA = lowest shared ancestor [OK]

Hint: LCA is the closest shared parent node [OK]

Common Mistakes:

• Confusing LCA with root node
• Thinking LCA is the node with highest value
• Assuming LCA must be a leaf node

2. Which of the following is the correct TypeScript function signature to find the LCA in a binary tree node structure?

easy

A. function findLCA(root: TreeNode, p: TreeNode, q: TreeNode): TreeNode | null

B. function findLCA(root: TreeNode, p: number, q: number): number

C. function findLCA(root: TreeNode): TreeNode

D. function findLCA(p: TreeNode, q: TreeNode): TreeNode

Solution

1. Step 1: Analyze parameters needed for LCA

   To find LCA, we need the root of the tree and the two nodes (p and q) to find the ancestor for.

2. Step 2: Check return type

   The function should return the TreeNode that is the LCA or null if not found.

3. Final Answer:

   function findLCA(root: TreeNode, p: TreeNode, q: TreeNode): TreeNode | null -> Option A

4. Quick Check:

   Correct signature includes root, p, q nodes and returns TreeNode or null [OK]

Hint: LCA function needs root and two nodes as input [OK]

Common Mistakes:

• Missing root parameter
• Using wrong parameter types like numbers instead of nodes
• Returning wrong type like number instead of TreeNode

3. Given the following TypeScript code for LCA, what will be the output if we call findLCA(root, node5, node1) where node5 and node1 are nodes with values 5 and 1 respectively?

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

function findLCA(root: TreeNode | null, p: TreeNode, q: TreeNode): TreeNode | null {
  if (!root || root === p || root === q) return root;
  const left = findLCA(root.left, p, q);
  const right = findLCA(root.right, p, q);
  if (left && right) return root;
  return left ? left : right;
}

// Tree structure:
//       3
//      / \
//     5   1
//    / \ / \
//   6  2 0  8
//     / \
//    7   4

const root = new TreeNode(3);
const node5 = new TreeNode(5);
const node1 = new TreeNode(1);
root.left = node5;
root.right = node1;
// ... other nodes assigned similarly

const lca = findLCA(root, node5, node1);
console.log(lca?.val);

medium

A. 3

B. 5

C. 1

D. null

Solution

1. Step 1: Trace recursive calls for nodes 5 and 1

   Starting at root (3), left subtree contains node 5, right subtree contains node 1. Both left and right recursive calls return non-null nodes.

2. Step 2: Determine LCA based on recursive returns

   Since both left and right calls return nodes, current root (3) is the LCA.

3. Final Answer:

   3 -> Option A

4. Quick Check:

   LCA of 5 and 1 is 3 [OK]

Hint: If nodes are in different subtrees, LCA is root [OK]

Common Mistakes:

• Returning one of the nodes instead of their ancestor
• Confusing node values with node references
• Ignoring null checks in recursion

4. Identify the bug in the following TypeScript LCA function and select the correct fix:

function findLCA(root: TreeNode | null, p: TreeNode, q: TreeNode): TreeNode | null {
  if (!root) return null;
  if (root.val === p.val || root.val === q.val) return root;
  const left = findLCA(root.left, p, q);
  const right = findLCA(root.right, p, q);
  if (left && right) return root;
  return left || right;
}

medium

A. Add a base case to return root when root is null

B. Replace logical OR with AND in return statement

C. Change comparisons to check node references, not values

D. Remove recursive calls to left and right subtrees

Solution

1. Step 1: Analyze node comparison logic

   The function compares node values (root.val === p.val), but nodes should be compared by reference to handle duplicates correctly.

2. Step 2: Correct the comparison to use reference equality

   Change to (root === p || root === q) to compare actual nodes, not just values.

3. Final Answer:

   Change comparisons to check node references, not values -> Option C

4. Quick Check:

   Node reference comparison fixes LCA correctness [OK]

Hint: Compare nodes by reference, not by value [OK]

Common Mistakes:

• Comparing node values instead of references
• Misusing logical operators in return
• Removing necessary recursion

5. You have a binary tree where nodes can have duplicate values. Which approach ensures correct Lowest Common Ancestor (LCA) identification for two given nodes p and q?

hard

A. Compare nodes by their values during recursion

B. Ignore duplicates and return the root as LCA

C. Return the node with the smaller value as LCA

D. Use node references (memory addresses) for comparison

Solution

1. Step 1: Understand the problem with duplicate values

   When values repeat, comparing nodes by value can lead to wrong LCA because multiple nodes share the same value.

2. Step 2: Use node references to uniquely identify nodes

   Comparing nodes by their references (actual objects) ensures the correct nodes are identified regardless of value duplicates.

3. Final Answer:

   Use node references (memory addresses) for comparison -> Option D

4. Quick Check:

   Reference comparison handles duplicates correctly [OK]

Hint: Use node references to handle duplicates safely [OK]

Common Mistakes:

• Comparing only node values
• Assuming smaller value node is LCA
• Ignoring duplicates in tree