Lowest Common Ancestor in Binary Tree in DSA Go

Mental Model

Find the closest shared parent node of two given nodes in a tree by checking where their paths meet.

Analogy: Imagine a family tree where you want to find the closest common grandparent of two cousins by tracing their parents upwards until they meet.

      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 top to find where paths to 5 and 1 diverge

Step 2: Recursively search left subtree for nodes 5 or 1

5 ↑
/ \
6  2
...

Why: Check if left subtree contains either node

Step 3: Found node 5 in left subtree, return node 5 up

Returning node 5 from left subtree

Why: One target found, propagate upwards

Step 4: Recursively search right subtree for nodes 5 or 1

1 ↑
/ \
0  8

Why: Check if right subtree contains either node

Step 5: Found node 1 in right subtree, return node 1 up

Returning node 1 from right subtree

Why: Second target found, propagate upwards

Step 6: At node 3, left returned 5 and right returned 1, so 3 is LCA

3 is lowest common ancestor of 5 and 1

Why: Both targets found in different subtrees, so current node is LCA

Result:

3
Final answer: Lowest Common Ancestor is node 3

Annotated Code

DSA Go

package main

import "fmt"

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

func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
	if root == nil || root == p || root == q {
		return root // base case: found p or q or reached leaf
	}

	left := lowestCommonAncestor(root.Left, p, q) // search left subtree
	right := lowestCommonAncestor(root.Right, p, q) // search right subtree

	if left != nil && right != nil {
		return root // p and q found in different subtrees, root is LCA
	}

	if left != nil {
		return left // p and q both in left subtree
	}

	return right // p and q both in right subtree or none found
}

func main() {
	// Construct the tree
	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.Left.Right.Left = &TreeNode{Val: 7}
	root.Left.Right.Right = &TreeNode{Val: 4}
	root.Right.Left = &TreeNode{Val: 0}
	root.Right.Right = &TreeNode{Val: 8}

	p := root.Left       // node 5
	q := root.Right      // node 1

	lca := lowestCommonAncestor(root, p, q)
	fmt.Printf("Lowest Common Ancestor of %d and %d is %d\n", p.Val, q.Val, lca.Val)
}

if root == nil || root == p || root == q {

stop recursion if current node is null or matches p or q

left := lowestCommonAncestor(root.Left, p, q)

search left subtree for p or q

right := lowestCommonAncestor(root.Right, p, q)

search right subtree for p or q

if left != nil && right != nil {

if p and q found in different subtrees, current node is LCA

if left != nil {

if both found in left subtree, return left

return right

otherwise return right subtree result

Output

Lowest Common Ancestor of 5 and 1 is 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 nil or the node that exists; no false LCA

DSA Go

if root == nil || root == p || root == q {

Both nodes are the same

Returns that node as LCA immediately

DSA Go

if root == nil || root == p || root == q {

Tree with only root node

If p and q are root, returns root; else nil

DSA Go

if root == nil || root == p || root == q {

When to Use This Pattern

When asked to find the closest shared ancestor of two nodes in a tree, use the Lowest Common Ancestor pattern by recursive subtree search to identify where paths split.

Common Mistakes

Mistake: Returning the first found node without checking both subtrees
Fix: Check both left and right subtree results before deciding LCA

Mistake: Not handling the base case when root matches p or q
Fix: Add base case to return root if it matches p or q

Summary

Finds the lowest node in a binary tree that is an ancestor of two given nodes.

Use when you need to find the closest shared parent of two nodes in a tree.

The key insight is that if one node is found in each subtree, the current node is their lowest common ancestor.