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.

Practice

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

easy

A. The node with the smallest value between the two nodes

B. The root node of the binary tree

C. The deepest node that is an ancestor of both nodes

D. The node that is a child of both nodes

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: Identify the deepest common ancestor

   Among all common ancestors, the LCA is the one farthest from the root (deepest).

3. Final Answer:

   The deepest node that is an ancestor of both nodes -> Option C

4. Quick Check:

   LCA = deepest common ancestor [OK]

Hint: LCA is the lowest node common to both paths [OK]

Common Mistakes:

• Confusing LCA with root node always
• Thinking LCA is the node with smaller value
• Assuming LCA is a child of both nodes

2. Which of the following is the correct Go function signature to find the LCA of two nodes in a binary tree?

easy

A. func lowestCommonAncestor(root TreeNode, p *TreeNode, q TreeNode) *TreeNode

B. func lowestCommonAncestor(root TreeNode, p TreeNode, q TreeNode) TreeNode

C. func lowestCommonAncestor(root *TreeNode, p TreeNode, q *TreeNode) TreeNode

D. func lowestCommonAncestor(root *TreeNode, p *TreeNode, q *TreeNode) *TreeNode

Solution

1. Step 1: Understand pointer usage in Go for tree nodes

   Tree nodes are usually passed as pointers to avoid copying and to allow modification.

2. Step 2: Check parameter and return types

   The function should accept pointers to TreeNode for root, p, and q, and return a pointer to TreeNode.

3. Final Answer:

   func lowestCommonAncestor(root *TreeNode, p *TreeNode, q *TreeNode) *TreeNode -> Option D

4. Quick Check:

   Use pointers for nodes in Go function signature [OK]

Hint: Use pointers for tree nodes in Go functions [OK]

Common Mistakes:

• Passing nodes by value instead of pointer
• Mixing pointer and value types in parameters
• Returning value instead of pointer

3. Given the following Go code snippet, what will be the output when finding the LCA of nodes 5 and 1?

type TreeNode struct {
    Val int
    Left, Right *TreeNode
}

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
}

func main() {
    root := &TreeNode{Val: 3}
    root.Left = &TreeNode{Val: 5}
    root.Right = &TreeNode{Val: 1}
    root.Left.Left = &TreeNode{Val: 6}
    root.Left.Right = &TreeNode{Val: 2}
    root.Right.Left = &TreeNode{Val: 0}
    root.Right.Right = &TreeNode{Val: 8}

    lca := lowestCommonAncestor(root, root.Left, root.Right)
    fmt.Println(lca.Val)
}

medium

A. 3

B. 5

C. 1

D. 2

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.

2. Step 2: Both left and right recursive calls return non-nil nodes

   Since left and right are both non-nil, root (3) is the LCA.

3. Final Answer:

   3 -> Option A

4. Quick Check:

   LCA(5,1) = 3 [OK]

Hint: If both sides return nodes, root is LCA [OK]

Common Mistakes:

• Returning one of the nodes instead of root
• Confusing node values with LCA
• Not handling nil checks properly

4. The following Go function is intended to find the LCA of two nodes in a binary tree. What is the bug?

func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
    if root == nil {
        return nil
    }
    if root.Val == p.Val || root.Val == q.Val {
        return root
    }
    left := lowestCommonAncestor(root.Left, p, q)
    right := lowestCommonAncestor(root.Right, p, q)
    if left != nil {
        return left
    }
    if right != nil {
        return right
    }
    return root
}

medium

A. Returns root when both left and right are nil instead of nil

B. Does not check for nil root at start

C. Compares node pointers instead of values

D. Does not recurse on left subtree

Solution

1. Step 1: Analyze return conditions after recursion

   If both left and right are nil, the function incorrectly returns root instead of nil.

2. Step 2: Understand correct base case for no ancestor found

   When neither subtree contains p or q, function should return nil, not root.

3. Final Answer:

   Returns root when both left and right are nil instead of nil -> Option A

4. Quick Check:

   Return nil if no ancestor found [OK]

Hint: Return nil if both sides are nil, not root [OK]

Common Mistakes:

• Returning root instead of nil when no match
• Missing nil check at start
• Comparing values instead of pointers incorrectly

5. You have a binary tree where nodes can have duplicate values. How should you modify the LCA function to correctly find the LCA of two given nodes p and q?

hard

A. Compare node values only since duplicates don't affect LCA

B. Compare node pointers instead of node values to identify nodes

C. Use node values and parent pointers to find LCA

D. Return the node with smaller value as LCA

Solution

1. Step 1: Understand problem with duplicate values

   When values are duplicated, comparing values alone can confuse nodes.

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

   Comparing pointers ensures the exact nodes p and q are found, not just matching values.

3. Step 3: Modify function to compare pointers (e.g., root == p)

   This guarantees correct LCA even with duplicate values.

4. Final Answer:

   Compare node pointers instead of node values to identify nodes -> Option B

5. Quick Check:

   Use pointers, not values, for unique node identity [OK]

Hint: Use pointers to identify nodes uniquely with duplicates [OK]

Common Mistakes:

• Comparing only values causing wrong LCA
• Assuming duplicates don't affect LCA
• Using parent pointers unnecessarily