Lowest Common Ancestor in Binary Tree + DFS Optimization

Problem Statement

Given a binary tree and two nodes p and q, find their Lowest Common Ancestor (LCA) — the deepest node that is an ancestor of both p and q (a node can be an ancestor of itself).

Follow-up: Once you find the LCA, compute the distance from p to q by running DFS from the LCA to both nodes.

Example 1:

Input: root = [3, 5, 1, 6, 2, 0, 8, null, null, 7, 4], p = 5, q = 1
Output: 3
Explanation: LCA of 5 and 1 is 3.

Example 2:

Input: root = [3, 5, 1, 6, 2, 0, 8, null, null, 7, 4], p = 5, q = 4
Output: 5
Explanation: LCA of 5 and 4 is 5 (a node can be its own ancestor).

Constraints:

• Number of nodes: [2, 10^5]
• All node values are unique.
• p != q and both exist in the tree.

Difficulty: Medium (LC 236)

---

Pattern Recognition

• What is the input structure? A binary tree with unique values.
• What are we optimizing? Finding the deepest shared ancestor, then optionally computing distances.
• What pattern does this fit? Recursive DFS with post-order traversal. Each subtree reports whether it contains p, q, or both.
• Why does this pattern fit? The LCA is the first node (going bottom-up) where p and q are found in different subtrees (or one is the node itself). Post-order traversal naturally propagates information upward.

---

Approach

Brute Force — Store Paths

Find the path from root to p and from root to q. Compare the two paths to find the last common node.

function lcaBrute(root, p, q):
    pathP = findPath(root, p)
    pathQ = findPath(root, q)
    lca = null
    for i in range(min(len(pathP), len(pathQ))):
        if pathP[i] == pathQ[i]:
            lca = pathP[i]
        else:
            break
    return lca

Time: O(n) — two traversals plus path comparison. Space: O(n) — storing two paths, each up to O(n) in a skewed tree. Why insufficient: The space usage is O(n). We can do this in O(h) space where h is tree height.

Optimal — Recursive DFS

Key Insight: At each node, recursively check the left and right subtrees. If p is found in one subtree and q in the other, the current node is the LCA. If both are in the same subtree, the LCA is in that subtree. If the current node is p or q, it is the LCA.

Step-by-step:

1. Base case: if node is None, return None.
2. If node is p or q, return node.
3. Recurse on left and right children.
4. If both left and right return non-None, current node is the LCA.
5. If only one side returns non-None, propagate that result up.

function lca(node, p, q):
    if node is None or node == p or node == q:
        return node
    left = lca(node.left, p, q)
    right = lca(node.right, p, q)
    if left and right: return node      # Found one in each subtree
    return left if left else right       # Both in same subtree

Time: O(n) — visit each node at most once. Space: O(h) — recursion stack, where h is tree height.

Follow-up — Distance Between Two Nodes via LCA

Once you have the LCA, run DFS from the LCA to find the depth of p and q relative to the LCA. The distance between p and q is depth(p) + depth(q).

function distFromLCA(node, target, depth):
    if node is None: return -1
    if node == target: return depth
    left = distFromLCA(node.left, target, depth + 1)
    if left != -1: return left
    return distFromLCA(node.right, target, depth + 1)

---

Walkthrough

        3
       / \
      5   1
     / \ / \
    6  2 0  8
      / \
     7   4

Finding LCA of p = 7 and q = 8:

Call Stack	Node	Left Result	Right Result	Return
lca(6, 7, 8)	6	None	None	None
lca(7, 7, 8)	7	—	—	7 (base case: node == p)
lca(4, 7, 8)	4	None	None	None
lca(2, 7, 8)	2	7 (from left=7)	None (from right=4)	7 (propagate left)
lca(5, 7, 8)	5	None (from left=6)	7 (from right=2)	7 (propagate right)
lca(0, 7, 8)	0	None	None	None
lca(8, 7, 8)	8	—	—	8 (base case: node == q)
lca(1, 7, 8)	1	None (from left=0)	8 (from right=8)	8 (propagate right)
lca(3, 7, 8)	3	7 (from left=5)	8 (from right=1)	3 (both non-None → LCA!)

LCA = 3.

Follow-up — Distance:

• DFS from 3 to 7: depth = 3 (3 → 5 → 2 → 7)
• DFS from 3 to 8: depth = 2 (3 → 1 → 8)
• Distance = 3 + 2 = 5

---

Implementation

TypeScript

class TreeNode {
    val: number;
    left: TreeNode | null;
    right: TreeNode | null;
    constructor(val = 0, left: TreeNode | null = null, right: TreeNode | null = null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

function lowestCommonAncestor(
    root: TreeNode | null, p: TreeNode, q: TreeNode
): TreeNode | null {
    // Base case: reached a leaf's child, or found p or q
    if (root === null || root === p || root === q) return root;

    const left = lowestCommonAncestor(root.left, p, q);
    const right = lowestCommonAncestor(root.right, p, q);

    // If both sides found something, this node is the LCA
    if (left && right) return root;

    // Otherwise, propagate whichever side found something
    return left ?? right;
}

function distanceBetweenNodes(root: TreeNode, p: TreeNode, q: TreeNode): number {
    const lca = lowestCommonAncestor(root, p, q)!;

    function depthTo(node: TreeNode | null, target: TreeNode, d: number): number {
        if (node === null) return -1;
        if (node === target) return d;
        // Search left first; if found, no need to search right
        const left = depthTo(node.left, target, d + 1);
        if (left !== -1) return left;
        return depthTo(node.right, target, d + 1);
    }

    return depthTo(lca, p, 0) + depthTo(lca, q, 0);
}

C++

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    // Base case: reached a leaf's child, or found p or q
    if (!root || root == p || root == q) return root;

    TreeNode* left = lowestCommonAncestor(root->left, p, q);
    TreeNode* right = lowestCommonAncestor(root->right, p, q);

    // If both sides found something, this node is the LCA
    if (left && right) return root;

    // Otherwise, propagate whichever side found something
    return left ? left : right;
}

int depthTo(TreeNode* node, TreeNode* target, int d) {
    if (!node) return -1;
    if (node == target) return d;
    // Search left first; if found, no need to search right
    int left = depthTo(node->left, target, d + 1);
    if (left != -1) return left;
    return depthTo(node->right, target, d + 1);
}

int distanceBetweenNodes(TreeNode* root, TreeNode* p, TreeNode* q) {
    TreeNode* lca = lowestCommonAncestor(root, p, q);
    return depthTo(lca, p, 0) + depthTo(lca, q, 0);
}

Watch out:

1. Comparing node values vs node references. The problem gives you node references, not values. Use root == p, not root.val == p.val, unless values are guaranteed unique and you are given values.
2. Not handling the case where one node is an ancestor of the other. The base case root == p or root == q handles this — the ancestor itself is the LCA. Do not skip this check.
3. Returning too early in the follow-up DFS. When computing depth, search left first. If found, return immediately without searching right. This is the optimization — you avoid unnecessary traversal.

---

Complexity Analysis

	Time	Space
Brute Force (Store Paths)	O(n)	O(n)
Optimal (Recursive DFS)	O(n)	O(h)
Follow-up (LCA + Distance)	O(n)	O(h)

Bottleneck: The time is O(n) in the worst case because you may need to visit every node. The space depends on tree height: O(log n) for balanced trees, O(n) for skewed trees. The follow-up adds at most two more O(h) DFS passes, so the overall complexity does not change.

---

Edge Cases

1. p is an ancestor of q (or vice versa) — The LCA is the ancestor node itself. Distance = depth difference.
2. p and q are siblings — LCA is their parent. Distance = 2.
3. p and q are the same node — LCA is that node. Distance = 0. (Problem says p != q, but worth mentioning.)
4. Skewed tree (linked list shape) — Recursion depth is O(n). Consider iterative approach if stack overflow is a concern.
5. p and q are leaves at maximum depth — LCA could be the root. Tests the full traversal.
6. Tree with only 2 nodes — Minimal case. Root is parent, other is child. LCA is root.

---

Related Problems

• LC 235 — LCA of a Binary Search Tree — Same concept but BST property allows O(h) without visiting all nodes.
• LC 1644 — LCA of a Binary Tree II — Nodes may not exist in the tree. Must verify existence before returning.
• LC 1650 — LCA of a Binary Tree III — Nodes have parent pointers. Reduces to "intersection of two linked lists."
• LC 863 — All Nodes Distance K in Binary Tree — Uses LCA-like parent tracking + BFS for distance-based queries.

---

What is Expected at Each Level

Junior: Write the recursive LCA solution with guidance. Understand why both subtrees must be checked. May not consider the ancestor-of-other edge case.

Mid-level: Write the LCA solution cleanly and immediately. Implement the distance follow-up. Discuss time/space trade-offs and handle edge cases. Mention the BST variant optimization.

Senior: Solve both parts quickly. Discuss iterative LCA (using parent pointers or Euler tour + sparse table for O(1) queries). Extend to LCA for n-ary trees. Discuss batch LCA queries using Tarjan's offline algorithm. Analyze when recursive depth is a concern and propose solutions.