Pattern #44

Lowest Common Ancestor

Important interview questions, thinking patterns, Deepest Common Ancestor rules, BST Split-Point logic, Parent Pointers (LL Intersection), and Go code templates.

Must Solve

10 core questions — solve these first.

1.Lowest Common Ancestor of a Binary Tree
Postorder DFS: if root == p || root == q return root; if left != nil && right != nil return rootmedium
2.Lowest Common Ancestor of a Binary Search Tree
BST split point: if both < curr go Left, if both > curr go Right, else return curreasy
3.Lowest Common Ancestor of Deepest Leaves
Postorder DFS returning (depth, lcaNode) tuplemedium
4.Smallest Subtree with all the Deepest Nodes
Same as LCA of Deepest Leaves: compare left & right max depthsmedium
5.Lowest Common Ancestor of a Binary Tree III
Parent pointers: Linked list intersection two-pointer trick (a = p, b = q)medium
6.Lowest Common Ancestor of a Binary Tree IV
LCA of slice of nodes: HashSet of targets + DFS returning non-nil countmedium
7.Lowest Common Ancestor with Parent Pointers
Store ancestors of p in HashSet or use two-pointer chain traversalmedium
8.Distance Between Two Nodes in a Binary Tree
dist(a, b) = dist(LCA, a) + dist(LCA, b)medium
9.Directions From One Binary Tree Node to Another
Find LCA -> start to LCA is all "U"s + LCA to dest is "L"/"R" stringmedium
10.All Nodes Distance K in Binary Tree
Convert tree to graph with parent pointers + BFS from target nodemedium

Also Important

5 more questions worth practicing.

11.LCA of Multiple Nodes
HashSet of target nodes + Postorder DFS returning node or nilmedium
12.LCA in N-ary Tree
Iterate all children: if > 1 child returns non-nil, current node is LCAmedium
13.Find Distance Between Two BST Nodes
Find BST LCA first -> sum depths from LCA to node1 and node2easy
14.Kth Ancestor of a Tree Node
Binary Lifting precomputing up[node][k] = 2^k ancestorhard
15.Binary Lifting for Multiple LCA Queries
O(N log N) preprocessing + O(log N) LCA query for massive query loadshard

How to Think

Two nodes in a normal Binary Tree?DFS + answers return upward
Two nodes in a BST?Use ordering + find split point
Nodes have parent pointers?Linked List Intersection thinking
Many LCA queries on the same large tree?Preprocessing + Binary Lifting

Go LCA Code Templates

Binary Tree LCA & BST LCA in Go

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

// 1. Normal Binary Tree LCA (Postorder DFS)
func lowestCommonAncestorBT(root, p, q *TreeNode) *TreeNode {
    if root == nil || root == p || root == q {
        return root
    }

    left := lowestCommonAncestorBT(root.Left, p, q)
    right := lowestCommonAncestorBT(root.Right, p, q)

    if left != nil && right != nil {
        return root // Both branches found targets -> Current node is LCA!
    }
    if left != nil {
        return left
    }
    return right
}

// 2. Binary Search Tree LCA (Split-Point Iterative)
func lowestCommonAncestorBST(root, p, q *TreeNode) *TreeNode {
    curr := root
    for curr != nil {
        if p.Val < curr.Val && q.Val < curr.Val {
            curr = curr.Left
        } else if p.Val > curr.Val && q.Val > curr.Val {
            curr = curr.Right
        } else {
            return curr // Split point!
        }
    }
    return nil
}

👉 Total Time: O(N) BT, O(H) BST | Space: O(H) stack

Binary Tree vs BST LCA Rules

1. Normal Binary Tree: No ordering exists. You MUST search both left and right subtrees. If both return non-nil pointers, the current node is the LCA. If only one returns non-nil, pass that pointer upward.

2. Binary Search Tree (BST): Leverage ordering! If both p and q values are smaller than curr.Val, move Left. If both are larger, move Right. The first node where their values split on opposite sides is the LCA!

Parent Pointers & Binary Lifting

1. Parent Pointers (LL Intersection): When nodes store a Parent pointer, tracing upward creates two linked lists. Using two pointers (a = p, b = q) that switch starting nodes when hitting nil finds the LCA at their meeting point!

2. Binary Lifting (Massive Queries): For large static trees with 100,000+ LCA queries, precompute up[node][k] (the 2^k-th ancestor) in O(N log N) time to answer each LCA query in O(log N)!

Visual Memory Rule

Lowest           → Deepest shared ancestor (NOT smallest value!)
Binary Tree      → Search both sides; if left != nil && right != nil -> LCA = root
BST              → First split point where p & q lie on opposite sides
Parent Pointers  → Two-pointer linked list intersection trick
Binary Lifting   → Precompute 2^k ancestors for O(log N) queries

💡 Golden Rule: "The LCA is the lowest node where the paths to the targets come together — or, viewed downward, where they first split apart."

Common Interview Mistakes

1. Thinking Lowest Means Smallest Value

"Lowest" means the deepest node in the tree structure that is an ancestor of both targets. It has nothing to do with node values.

2. Forgetting a Target Can Be An Ancestor

If node p is an ancestor of q, then p is the LCA! Returning root immediately when root == p || root == q handles this cleanly.

3. Applying BST Logic to Normal Binary Trees

In general binary trees, node values do NOT determine left/right child placement! Only use BST comparisons (p.Val < curr.Val) when BST property is explicitly guaranteed.

4. Comparing Node Values Instead of Pointers

If duplicate node values exist in the tree, comparing node.Val == p.Val causes incorrect matches! Always compare node pointer identities (node == p).

Interview Rules

1. Closest shared ancestor needed? → Lowest Common Ancestor (LCA)
2. Binary Tree LCA rule? → Search both sides; if left != nil && right != nil return current node
3. Target node equals root? → Return root immediately (node can be ancestor of itself!)
4. BST LCA rule? → Find first split point where p & q lie on opposite sides
5. Parent pointers present? → Two-pointer linked list intersection trick
6. Distance between two nodes? → dist(a, b) = dist(LCA, a) + dist(LCA, b)
7. Directions start to dest? → start -> LCA ("U"s) + LCA -> dest("L"/"R" path)
8. Overall Complexity → Time: O(N) | Stack Space: O(H) (O(log N) balanced, O(N) skewed)

Small Rules

Rule 1: LCA is the deepest shared ancestor in the tree structure.
Rule 2: A target node can serve as its own ancestor.
Rule 3: In Binary Trees, LCA is the node where left and right returns are both non-nil.
Rule 4: In BSTs, LCA is the first node where target values split directions.
Rule 5: Parent pointer LCA reduces to Linked List Intersection.

Production Thinking

Organization Management Hierarchies → Finding nearest shared manager between engineering & finance team members

File System Common Path Resolution → Locating closest common directory path between /app/src/auth and /app/src/payments (/app/src)

UI Component Container Trees → Finding nearest shared UI layout container holding both a Button and Input field

Taxonomy & Category Trees → Identifying lowest common product classification node in e-commerce catalogs

Remember This

LCA             → Lowest shared ancestor
Binary Tree     → Search Left + Right
Both sides found→ Current node is LCA
One side found  → Return pointer upward
BST             → First split point
Both smaller    → Go Left
Both larger     → Go Right
Parent pointers → Linked list intersection
Many queries    → Binary Lifting (O(log N))
Time            → O(N)

💡 Golden Rule: "The LCA is the lowest node where the paths to the targets come together — or, viewed downward, where they first split apart."