Lowest Common Ancestor in Binary Tree in DSA Typescript - Execution Trace

Concept Flow - Lowest Common Ancestor in Binary Tree

Start at root node

↓

Check if root is null or matches p or q

Yes↓

Return root as LCA candidate

No↓

Recurse left subtree

↓

Recurse right subtree

↓

If both left and right recursion return non-null

↓

Current node is LCA

↓

Return non-null child from left or right

↓

End

Start from root, check if it matches either node. Recurse left and right. If both sides find nodes, current is LCA. Otherwise, return the found node.

Execution Sample

DSA Typescript

function lowestCommonAncestor(root, p, q) {
  if (!root || root === p || root === q) return root;
  const left = lowestCommonAncestor(root.left, p, q);
  const right = lowestCommonAncestor(root.right, p, q);
  if (left && right) return root;
  return left || right;
}

Finds the lowest common ancestor of nodes p and q in a binary tree by recursive search.

Execution Table

Step	Operation	Node Visited	Left Recursion Result	Right Recursion Result	LCA Decision	Visual State
1	Start at root	3	?	?	Recurse left and right	3
2	Recurse left	5	?	?	Recurse left and right	3 -> 5
3	Recurse left of 5	6	null	null	Return 6	3 -> 5 -> 6
4	Recurse right of 5	2	null	null	Return 2	3 -> 5 -> 6,2
5	At node 5	5	6	2	Both sides non-null, return 5 as LCA	3 -> 5(LCA)
6	Recurse right of 3	1	?	?	Recurse left and right	3(LCA) -> 1
7	Recurse left of 1	0	null	null	Return 0	3(LCA) -> 1 -> 0
8	Recurse right of 1	8	null	null	Return 8	3(LCA) -> 1 -> 0,8
9	At node 1	1	0	8	Both sides non-null, return 1	3(LCA) -> 1
10	At root 3	3	5	1	Both sides non-null, return 3 as LCA	3(LCA)
11	End	3	5	1	LCA found: 3	3(LCA)

💡 Recursion ends when all nodes visited and LCA found at node 3 where left and right recursion both found target nodes.

Variable Tracker

Variable	Start	After Step 3	After Step 5	After Step 9	After Step 10	Final
root	3	5	5	1	3	3
left	?	6	5	0	5	5
right	?	2	2	8	1	1
LCA	null	null	5	1	3	3

Key Moments - 3 Insights

Why do we return the node itself if root matches p or q?

Because if the current node is p or q, it could be the ancestor or one of the targets. Returning it helps identify if this path contains p or q, as shown in execution_table steps 1 and 3.

Why do we return root when both left and right recursion results are non-null?

Because it means p and q are found in different subtrees of the current node, so this node is their lowest common ancestor. See execution_table step 5 and 10.

What if only one side returns a non-null node?

We return that non-null node upwards because it means both p and q are in that subtree or that subtree contains one of them. This is shown in steps 9 and 10.

Visual Quiz - 3 Questions

Look at the execution_table at step 5, what is the LCA decision?

A Return node 5 as LCA because both left and right are non-null

B Return null because no target found

C Return node 6 because it is left child

D Return node 2 because it is right child

💡 Hint

Check the 'LCA Decision' column at step 5 in execution_table

At which step does the recursion find the final LCA node 3?

A Step 3

B Step 5

C Step 10

D Step 7

💡 Hint

Look at the 'LCA Decision' and 'Node Visited' columns in execution_table

If node q was not in the tree, how would the LCA change in the variable_tracker?

A LCA would be null at the end

B LCA would be node p

C LCA would be root node 3 anyway

D LCA would be node q

💡 Hint

Check how LCA is assigned when only one side returns a non-null node in variable_tracker

Concept Snapshot

Lowest Common Ancestor (LCA) in Binary Tree:
- Start at root node
- If root is null or matches p or q, return root
- Recursively find LCA in left and right subtrees
- If both sides return non-null, current node is LCA
- Else return non-null side
- Recursion ends when LCA found or subtree exhausted

Full Transcript

The Lowest Common Ancestor algorithm starts at the root node of the binary tree. If the current node is null or matches either of the target nodes p or q, it returns that node immediately. Otherwise, it recursively searches the left and right subtrees. If both recursive calls return non-null nodes, it means p and q are found in different subtrees, so the current node is their lowest common ancestor. If only one side returns a non-null node, that node is returned upwards as a candidate. This process continues until the recursion completes and the LCA is found. The execution table traces these recursive calls and decisions step-by-step, showing how the algorithm narrows down to the LCA node. The variable tracker records the state of key variables during execution. Key moments clarify why certain returns happen, helping beginners understand the recursion and decision points.

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