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

Concept Flow - Lowest Common Ancestor in Binary Tree

Start at root

↓

Check if root is nil or matches p or q

↓

If yes, return root

↓

Recurse left subtree

↓

Recurse right subtree

↓

If both left and right return non-nil

↓

Current node is LCA

↓

Else return non-nil child

↓

End

Start from root, check base cases, recurse left and right, if both sides find nodes, current is LCA, else return found node.

Execution Sample

DSA Go

func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
  if root == nil || root == p || root == q {
    return root
  }
  left := lowestCommonAncestor(root.Left, p, q)
  right := lowestCommonAncestor(root.Right, p, q)
  if left != nil && right != nil {
    return root
  }
  if left != nil {
    return left
  }
  return 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 Result	Right Result	Return Value	Tree State
1	Start at root	3	?	?	?	3
2	Check root == p or q	3	?	?	?	3
3	Recurse left subtree	5	?	?	?	3 -> 5
4	Check node 5 == p or q	5	?	?	5 (matches p)	3 -> 5
5	Return node 5 up	5	5	?	5	3 -> 5
6	Recurse right subtree	1	?	?	?	3 -> 5, 1
7	Check node 1 == p or q	1	?	?	1 (matches q)	3 -> 5, 1
8	Return node 1 up	1	?	1	1	3 -> 5, 1
9	Both left and right non-nil	3	5	1	3 (LCA)	3 -> 5, 1
10	Return LCA node 3	3	5	1	3	3 -> 5, 1
11	End recursion	-	-	-	3	3 -> 5, 1

💡 Both left and right recursive calls found p and q, so root 3 is LCA.

Variable Tracker

Variable	Start	After Step 3	After Step 5	After Step 6	After Step 8	Final
root	3	5	5	1	1	3
left	nil	5	5	5	5	5
right	nil	nil	nil	1	1	1
return	nil	nil	5	nil	1	3

Key Moments - 3 Insights

Why do we return root immediately if root == p or root == q?

Because if the current node is p or q, it could be the ancestor or one of the nodes itself. See execution_table step 4 where node 5 matches p and returns immediately.

Why do we check if both left and right recursive calls are non-nil?

Because if both sides find one of the nodes, the current node is their lowest common ancestor. See execution_table step 9 where left=5 and right=1, so root 3 is LCA.

What if only one side returns non-nil?

We return that non-nil node up because the other side didn't find anything. This is shown in steps 5 and 8 where only one side returns a node.

Visual Quiz - 3 Questions

Look at the execution_table at step 4, what is the return value and why?

A Returns node 5 because it matches p

B Returns nil because no match found

C Returns root node 3

D Returns node 1 because it matches q

💡 Hint

Check 'Return Value' column at step 4 in execution_table

At which step does the function determine the lowest common ancestor?

A Step 5

B Step 9

C Step 7

D Step 3

💡 Hint

Look for the step where both left and right results are non-nil in execution_table

If node q was not found in the tree, how would the return value at step 10 change?

A It would return node p (5)

B It would return nil

C It would return root (3)

D It would return node q (1)

💡 Hint

Refer to variable_tracker and execution_table logic when only one side returns a node

Concept Snapshot

Lowest Common Ancestor in Binary Tree:
- Recursively search left and right subtrees
- If current node is p or q, return it
- If both sides return non-nil, current node is LCA
- Else return non-nil child
- Base case: nil node returns nil

Full Transcript

The Lowest Common Ancestor (LCA) algorithm starts at the root node. If the root is nil or matches one of the target nodes p or q, it returns the root immediately. Otherwise, it recursively searches the left and right subtrees. If both recursive calls return non-nil nodes, it means p and q are found in different subtrees, so the current root is their LCA. If only one side returns a non-nil node, that node is returned up the recursion. The process continues until the LCA is found or the recursion ends. This is shown step-by-step in the execution table and variable tracker.