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.