Lowest Common Ancestor of a Binary Tree

Difficulty: Medium
Topics: Tree, Depth-First Search, Binary Tree
Link: https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/

Problem Description

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”

Example 1:


Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
Output: 3
Explanation: The LCA of nodes 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: The LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition.

Example 3:


Input: root = [1,2], p = 1, q = 2
Output: 1

Constraints:

The number of nodes in the tree is in the range [2, 105].
-109 <= Node.val <= 109
All Node.val are unique.
p != q
p and q will exist in the tree.

Solution

1. Problem Deconstruction (500+ words)

Technical Restatement
Given a binary tree structure where each node contains:

A unique integer value
Pointers to left and right child nodes
All nodes are accessible through root pointer

We must implement a function lowestCommonAncestor(root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode that locates the deepest node in the tree where:

Both p and q exist in its subtree (including the case where the node itself is p or q)
The solution must handle cases where one target node is an ancestor of the other
No assumptions can be made about tree balance or structure

Beginner-Friendly Restatement
Imagine a family tree where each person can have up to two children. We’re looking for the “youngest grandparent” that two specific people share. This shared grandparent could be one of the people themselves (if one person is the parent/grandparent of the other). We need to find this person by starting from the oldest ancestor and working our way down.

Mathematical Formulation
Let:

$T$ represent the binary tree with node set $V$
$descendants(v)$ = $\{v\} \cup descendants(left(v)) \cup descendants(right(v))$
$ancestors(v)$ = $\{v\} \cup ancestors(parent(v))$
$LCA(p,q)$ = $\underset{v \in V}{\arg\max}\, depth(v)$ subject to $p \in descendants(v)$ and $q \in descendants(v)$

Where $depth(root) = 0$ and $depth(child) = depth(parent) + 1$

Constraint Analysis

“Number of nodes in [2, 10^5]”: Eliminates O(n²) solutions; requires O(n) or O(h) where h is tree height
“Node values unique”: Enables value-based comparison but problem uses node identity
“p ≠ q”: Removes degenerate case handling
“p and q exist in tree”: No need for null checks on search failure
Hidden implication: Worst-case tree could be a linked list (height = n), so recursion depth must be considered

2. Intuition Scaffolding

Real-World Metaphor
In a corporate hierarchy, finding the LCA is like identifying the lowest-ranking manager that two employees both report to (directly or indirectly). This manager could be one of the employees themselves if one is the other’s supervisor.

Gaming Analogy
In a skill tree RPG, the LCA represents the most advanced common skill that two end-game skills both require. You must backtrack from both skills until you find where their prerequisite paths converge.

Math Analogy
Think of the tree as a partially ordered set where each node’s ancestors form a chain. The LCA is the maximal element in the intersection of the ancestor chains of p and q.

Common Pitfalls

Global variable misuse: Trying to store LCA in class variables breaks multiple calls
Path storage: Building full paths to root wastes O(n) space unnecessarily
Early termination: Returning when finding one node misses cases where other node is in subtree
Value comparison: Assuming BST properties when tree is unordered
Multiple traversals: Searching for p and q separately then comparing paths

3. Approach Encyclopedia

Brute Force - Path Comparison

def find_path(root, target, path):
    if not root: return False
    path.append(root)
    if root == target: return True
    if (find_path(root.left, target, path) or 
        find_path(root.right, target, path)): 
        return True
    path.pop()
    return False

def lca_brute(root, p, q):
    path_p, path_q = [], []
    find_path(root, p, path_p)
    find_path(root, q, path_q)
    
    lca = root
    for i in range(min(len(path_p), len(path_q))):
        if path_p[i] == path_q[i]:
            lca = path_p[i]
        else:
            break
    return lca

Time Complexity: O(n) + O(n) = O(n) for two DFS traversals
Space Complexity: O(h) + O(h) = O(h) for two paths, worst-case O(n)

Optimal - Single Pass Recursive

def lca_optimal(root, p, q):
    if not root or root == p or root == q:
        return root
    
    left = lca_optimal(root.left, p, q)
    right = lca_optimal(root.right, p, q)
    
    if left and right:  # p and q found in different subtrees
        return root
    return left or right  # Both in one subtree or None

Time Complexity Derivation:
Each node visited exactly once: T(n) = T(left) + T(right) + O(1)
Worst-case: T(n) = T(n-1) + O(1) → O(n)
Best-case (balanced): T(n) = 2T(n/2) + O(1) → O(n)

Space Complexity: O(h) recursion stack, worst-case O(n)

Visualization

        A
       / \
      B   C
     / \   \
    D   E   F
   
Find LCA(D, E):
A: left = LCA(B,D,E), right = LCA(C,D,E) = None
B: left = LCA(D,D,E) = D, right = LCA(E,D,E) = E
B has both non-null → return B
A receives B from left, None from right → return B

4. Code Deep Dive

def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
    # Base case: null node or found target
    if not root or root == p or root == q:
        return root  # Line 2-3: Terminal conditions
    
    # Recursive search in left and right subtrees
    left = self.lowestCommonAncestor(root.left, p, q)   # Line 4: DFS left
    right = self.lowestCommonAncestor(root.right, p, q) # Line 5: DFS right
    
    # Decision logic
    if left and right:    # Line 6: Current root is LCA
        return root
    elif left:            # Line 7: LCA in left subtree  
        return left
    else:                 # Line 8: LCA in right subtree
        return right

Edge Case Handling

Example 1 (p=5, q=1):
At node 3: left returns 5, right returns 1 → both non-null → return 3
Example 2 (p=5, q=4):
At node 5: root==p → return 5 immediately (LCA is p itself)
Example 3 (p=1, q=2):
At node 1: root==p → return 1 immediately

5. Complexity War Room

Hardware-Aware Analysis

Memory: 10⁵ nodes × (8B pointer × 3 + 8B value) ≈ 3.2MB tree structure
Stack: Worst-case 10⁵ recursion frames × 200B/frame ≈ 20MB (fits L3 cache)
Optimization: Tail recursion not possible due to multiple recursive calls

Industry Comparison Table

Approach	Time	Space	Readability	Interview Viability
Path Storage	O(n)	O(h)	8/10	✅ Acceptable
Single Pass Recursive	O(n)	O(h)	9/10	✅ Preferred
Iterative with Parent Pointers	O(n)	O(n)	6/10	⚠️ Over-engineered
Binary Lifting	O(n log n) pre	O(log n) query	4/10	❌ Overkill

6. Pro Mode Extras

Variants Section

LCA in BST: Use value comparisons to prune search space

def lca_bst(root, p, q):
    while root:
        if max(p.val, q.val) < root.val:
            root = root.left
        elif min(p.val, q.val) > root.val:
            root = root.right
        else:
            return root

LCA with Parent Pointers: Move up from both nodes to find intersection
LCA for K Nodes: Extend recursive approach to handle multiple targets
LCA with Path Queries: Answer LCA queries efficiently after O(n) preprocessing

Interview Cheat Sheet

First Mention: “This can be solved in O(n) time with O(h) space using post-order traversal”
Key Insight: “A node is the LCA if it has the targets in different subtrees or is one target itself”
Edge Cases: Always verify handling of (p is ancestor of q) and symmetric cases
Testing Strategy: Draw 5-node tree and trace execution for all node pairs

#236 - Lowest Common Ancestor of a Binary Tree