153. Lowest Common Ancestor of a Binary Tree
🔗 LeetCode Problem: 236. Lowest Common Ancestor of a Binary Tree
📊 Difficulty: Medium
🏷️ Topics: Binary Trees, DFS, LCA, Recursion, Tree Navigation
Problem Statement
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.
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, 10^5]
- -10^9 <= Node.val <= 10^9
- All Node.val are unique
- p != q
- p and q will exist in the tree
🌳 Visual Understanding - What is LCA?
Definition of Common Ancestor:
Tree:
3
/ \
5 1
/ \ / \
6 2 0 8
/ \
7 4
Ancestors of node 5: [5, 3]
Ancestors of node 1: [1, 3]
Common ancestors: [3]
Ancestors of node 7: [7, 2, 5, 3]
Ancestors of node 4: [4, 2, 5, 3]
Common ancestors: [2, 5, 3]
Lowest (deepest) common ancestor: 2
LCA = deepest node that's ancestor to both! 🔑
Visual Examples:
EXAMPLE 1: LCA(5, 1)
3 ← LCA! (lowest common ancestor)
/ \
5* 1* (both are descendants of 3)
/ \ / \
6 2 0 8
LCA = 3 ✓
EXAMPLE 2: LCA(5, 4)
3
/ \
5* ← LCA! (5 is ancestor of itself!)
/ \
6 2
/ \
7 4*
LCA = 5 ✓ (node can be ancestor of itself!)
EXAMPLE 3: LCA(7, 4)
3
/ \
5
/ \
6 2 ← LCA! (both in this subtree)
/ \
7* 4*
LCA = 2 ✓
Key Observations:
1. LCA is the "split point"
- Where paths to p and q diverge
- Deepest node where both are descendants
2. Node can be its own ancestor
- If p is ancestor of q (or vice versa)
- LCA = the higher node
3. LCA always exists
- Both nodes guaranteed in tree
- Root is always common ancestor (worst case)
This is about TREE NAVIGATION! 🎯
🧠 The AHA Moment - The Elegant Recursive Solution
The Core Insight:
At each node, ask three questions:
1. Is current node p or q?
→ If yes, this could be LCA!
2. Is p or q in left subtree?
→ Recurse left to find out
3. Is p or q in right subtree?
→ Recurse right to find out
If TWO of above are true:
→ Current node is LCA!
If ONE is true:
→ Return that one up (propagate the find)
If NONE are true:
→ Return null (neither found here)
Visual Decision Making:
At each node, three cases:
CASE 1: Found in BOTH subtrees
3 ← Current node
/ \
5* 1* (found p here) (found q here)
→ Current node IS the LCA! Return it!
CASE 2: Found in ONE subtree (or current)
3
/ \
5* null (found p here) (nothing here)
→ Return the found node up (propagate)
CASE 3: Found in NEITHER
8
/ \
null null (nothing) (nothing)
→ Return null up
The Beautiful Recursion:
The return value has dual meaning:
1. If LCA found: Return LCA
2. If only one found: Return that node
3. If neither found: Return null
Parent uses returns to decide:
- Both non-null → Parent is LCA
- One non-null → Propagate that one
- Both null → Propagate null
Elegant! ✨
🧠 Recursive Thinking - Building the Solution
Base Case:
When to stop?
1. Reached null → return null
2. Found p or q → return current node
if (node == null) return null;
if (node == p || node == q) return node;
Recursive Case:
For any node:
STEP 1: Recurse on left
left = lowestCommonAncestor(node.left, p, q)
STEP 2: Recurse on right
right = lowestCommonAncestor(node.right, p, q)
STEP 3: Decide based on returns
if (left != null && right != null):
→ Found in both subtrees!
→ Current node is LCA
→ return node
if (left != null):
→ Found only in left
→ return left
if (right != null):
→ Found only in right
→ return right
else:
→ Found in neither
→ return null
What Each Node Returns:
Returns one of:
1. The LCA (if both p and q found in subtree)
2. p or q (if only one found in subtree)
3. null (if neither found in subtree)
Parent interprets based on what children return!
Example:
Node 2 finds 7 in left, 4 in right
→ Returns itself (LCA!)
Node 5 finds 2 (which is LCA) in right, nothing in left
→ Returns 2 (propagate LCA up!)
🎯 Solution: Elegant Recursive Approach
Implementation:
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
// Base case 1: Reached null, neither p nor q here
if (root == null) {
return null;
}
// Base case 2: Found p or q
// Return immediately - this could be the LCA!
// WHY return early? If this is p, and q is below,
// then p is the LCA (node is ancestor of itself)
if (root == p || root == q) {
return root;
}
// STEP 1: Search in left subtree
// Will return:
// - LCA if both p and q found in left
// - p or q if only one found in left
// - null if neither found in left
TreeNode left = lowestCommonAncestor(root.left, p, q);
// STEP 2: Search in right subtree
// Same return semantics as left
TreeNode right = lowestCommonAncestor(root.right, p, q);
// STEP 3: Make decision based on what children returned
// CASE 1: Both returned non-null
// This means p in one subtree, q in other
// Current node is the split point = LCA!
if (left != null && right != null) {
return root;
}
// CASE 2: Only left returned non-null
// This means both p and q are in left subtree
// (or left already found the LCA)
// Propagate left's result upward
if (left != null) {
return left;
}
// CASE 3: Only right returned non-null
// This means both p and q are in right subtree
// (or right already found the LCA)
// Propagate right's result upward
if (right != null) {
return right;
}
// CASE 4: Both returned null
// Neither p nor q found in this subtree
return null;
}
}
Simplified Version:
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
// Base cases
if (root == null || root == p || root == q) {
return root;
}
// Recurse
TreeNode left = lowestCommonAncestor(root.left, p, q);
TreeNode right = lowestCommonAncestor(root.right, p, q);
// Decision
if (left != null && right != null) return root; // Found in both
return left != null ? left : right; // Return non-null one
}
}
🔍 Detailed Dry Run - Finding LCA(7, 4)
Tree:
3
/ \
5 1
/ \ / \
6 2 0 8
/ \
7* 4*
Find LCA of 7 and 4
Complete Call Stack Visualization:
═══════════════════════════════════════════════════
CALL STACK - FINDING LCA(7, 4)
═══════════════════════════════════════════════════
Level 0: LCA(3, 7, 4)
│
├─ 3 != null ✓
├─ 3 != 7 ✓
├─ 3 != 4 ✓
│
├─ LEFT: LCA(5, 7, 4) ────────────────────────────┐
│ │
│ Level 1: LCA(5, 7, 4) │
│ │ │
│ ├─ 5 != null ✓ │
│ ├─ 5 != 7 ✓ │
│ ├─ 5 != 4 ✓ │
│ │ │
│ ├─ LEFT: LCA(6, 7, 4) ───────────────────┐ │
│ │ │ │
│ │ Level 2: LCA(6, 7, 4) │ │
│ │ │ │ │
│ │ ├─ 6 != null ✓ │ │
│ │ ├─ 6 != 7 ✓ │ │
│ │ ├─ 6 != 4 ✓ │ │
│ │ │ │ │
│ │ ├─ LEFT: LCA(null, 7, 4) → null │ │
│ │ ├─ RIGHT: LCA(null, 7, 4) → null │ │
│ │ │ │ │
│ │ ├─ left = null, right = null │ │
│ │ └─ return null │ │
│ │ │ │
│ ├─ left = null │ │
│ │ │
│ ├─ RIGHT: LCA(2, 7, 4) ──────────────────┐ │
│ │ │ │
│ │ Level 2: LCA(2, 7, 4) │ │
│ │ │ │ │
│ │ ├─ 2 != null ✓ │ │
│ │ ├─ 2 != 7 ✓ │ │
│ │ ├─ 2 != 4 ✓ │ │
│ │ │ │ │
│ │ ├─ LEFT: LCA(7, 7, 4) ───────────┐ │ │
│ │ │ │ │ │
│ │ │ Level 3: LCA(7, 7, 4) │ │ │
│ │ │ │ │ │ │
│ │ │ ├─ 7 != null ✓ │ │ │
│ │ │ ├─ 7 == 7 ✓ FOUND! │ │ │
│ │ │ └─ return 7 │ │ │
│ │ │ │ │ │
│ │ ├─ left = 7 (node 7) │ │ │
│ │ │ │ │
│ │ ├─ RIGHT: LCA(4, 7, 4) ──────────┐ │ │
│ │ │ │ │ │
│ │ │ Level 3: LCA(4, 7, 4) │ │ │
│ │ │ │ │ │ │
│ │ │ ├─ 4 != null ✓ │ │ │
│ │ │ ├─ 4 == 4 ✓ FOUND! │ │ │
│ │ │ └─ return 4 │ │ │
│ │ │ │ │ │
│ │ ├─ right = 4 (node 4) │ │ │
│ │ │ │ │
│ │ ├─ Decision: left != null && right != null
│ │ ├─ BOTH FOUND! Current is LCA! │ │ │
│ │ └─ return 2 (node 2) ← LCA FOUND! │ │ │
│ │ │ │
│ ├─ right = 2 (node 2, which IS the LCA) │ │
│ │ │
│ ├─ Decision: left = null, right = 2 │
│ ├─ Only right non-null │
│ └─ return 2 (propagate LCA up) │
│ │
├─ left = 2 (the LCA!) │
│ │
├─ RIGHT: LCA(1, 7, 4) ───────────────────────────┐
│ │
│ Level 1: LCA(1, 7, 4) │
│ │ │
│ ├─ 1 != null ✓ │
│ ├─ 1 != 7 ✓ │
│ ├─ 1 != 4 ✓ │
│ │ │
│ ├─ LEFT: LCA(0, 7, 4) │
│ │ ... (explores, finds nothing) │
│ │ └─ return null │
│ │ │
│ ├─ RIGHT: LCA(8, 7, 4) │
│ │ ... (explores, finds nothing) │
│ │ └─ return null │
│ │ │
│ ├─ left = null, right = null │
│ └─ return null │
│ │
├─ right = null │
│ │
├─ Decision: left = 2, right = null │
├─ Only left non-null │
└─ return 2 │
═══════════════════════════════════════════════════
FINAL: Node 2 is the LCA of 7 and 4! ✓
═══════════════════════════════════════════════════
Return Value Propagation:
Node 7: returns 7 (found itself)
Node 4: returns 4 (found itself)
Node 2: left=7, right=4 → BOTH! → returns 2 (LCA!)
Node 6: returns null (neither found)
Node 5: left=null, right=2 → returns 2 (propagate)
Node 1: returns null (neither found)
Node 3: left=2, right=null → returns 2 (propagate)
Final answer: 2 ✓
🔍 Another Example - LCA(5, 1)
Tree:
3* ← Expected LCA
/ \
5* 1*
/ \ / \
6 2 0 8
Execution Flow:
Level 0: LCA(3, 5, 1)
│
├─ 3 != 5, 3 != 1
│
├─ LEFT: LCA(5, 5, 1)
│ ├─ 5 == 5 ✓ FOUND!
│ └─ return 5 (early return!)
│
├─ left = 5
│
├─ RIGHT: LCA(1, 5, 1)
│ ├─ 1 == 1 ✓ FOUND!
│ └─ return 1 (early return!)
│
├─ right = 1
│
├─ Decision: left = 5, right = 1
├─ BOTH non-null!
└─ return 3 (current node is LCA!)
Answer: 3 ✓
Why Early Return Works:
When we find p or q:
We return immediately without exploring children
This is CORRECT because:
1. If this node is LCA (other node below)
→ We return this node ✓
2. If LCA is above
→ Parent will see non-null from this side
→ Parent will decide correctly ✓
Early return is optimization AND correct! 🎯
📊 Complexity Analysis
Time Complexity: O(n)
Worst case: Visit every node
- Looking for p and q
- Might be at opposite ends
Each node visited once: O(n)
Space Complexity: O(h)
Recursion call stack: O(h)
Best case (balanced): O(log n)
Worst case (skewed): O(n)
No additional data structures!
⚠️ Common Mistakes
Mistake 1: Not Understanding Return Value Meaning
// ❌ CONCEPTUAL ERROR - Thinking return is just p or q
// Return value has THREE meanings:
// 1. LCA (if both found in subtree)
// 2. p or q (if only one found)
// 3. null (if neither found)
// Common misconception:
// "If we return node, it means we found it"
// WRONG! It might mean it's the LCA!
// ✓ CORRECT understanding:
// Return value = "What's important from this subtree"
// Could be LCA, could be one node, could be nothing
Mistake 2: Not Returning Early When Found
// ❌ WRONG - Continues after finding p or q
if (root == p || root == q) {
// Found it! But should we keep looking?
// NO! Return immediately!
}
// Why return early?
// If current is p and q is below:
// current is the LCA!
// If LCA is above:
// parent needs to know we found one here
// ✓ CORRECT - Return immediately
if (root == p || root == q) {
return root; ✓
}
Mistake 3: Wrong Logic for Decision
// ❌ WRONG - Incorrect conditions
if (left == p && right == q) { // WRONG!
return root;
}
// Problem: left/right might be LCA, not p/q!
// They return "important node from subtree"
// ✓ CORRECT - Check for non-null
if (left != null && right != null) { ✓
return root;
}
// If both non-null, current is split point!
Mistake 4: Not Handling Node as Its Own Ancestor
// ❌ WRONG - Special case for p == q ancestor
// Some try to add special logic:
if (root == p) {
// Check if q is below?
// Too complex!
}
// ✓ CORRECT - Algorithm handles it naturally!
// When we return root (found p),
// If q below, parent will see only one non-null
// Will propagate up until LCA found
// No special case needed! ✨
Mistake 5: Trying to Track Path
// ❌ WRONG - Overthinking with path tracking
List<TreeNode> pathToP = new ArrayList<>();
List<TreeNode> pathToQ = new ArrayList<>();
// Find paths, then compare...
// Too complex! O(n) space, multiple passes
// ✓ CORRECT - Single DFS with smart returns
// Current solution: One pass, O(h) space
// Much simpler! ✓
🎯 Pattern Recognition - LCA Problems
Core Pattern: Smart Return Values
Template for LCA-style problems:
private TreeNode solve(TreeNode node, ...) {
// Base cases
if (node == null) return null;
if (found_something) return node;
// Recurse
TreeNode left = solve(node.left, ...);
TreeNode right = solve(node.right, ...);
// Decision based on returns
if (both_found) return node;
return whichever_is_non_null;
}
Related Problems:
1. Lowest Common Ancestor of BST
Similar but simpler!
Use BST property:
- If both < root: LCA in left
- If both > root: LCA in right
- Otherwise: root is LCA
2. Lowest Common Ancestor of Deepest Leaves
Find LCA of deepest nodes
Similar return logic
Track depth alongside
3. Distance Between Nodes
Find LCA first
Calculate distance from LCA to both nodes
Sum distances
4. Path Between Nodes
Find LCA
Build path from p to LCA to q
Uses LCA as intermediate
When to Use This Pattern:
✓ Finding meeting point in tree
✓ Smart return values with multiple meanings
✓ Need to make decision based on subtree info
✓ Elegant single-pass solution
✓ Post-order traversal natural
📝 Quick Revision Notes
🎯 Core Concept
Find lowest (deepest) common ancestor of two nodes. LCA = deepest node having both p and q as descendants (node can be its own ancestor). Use elegant recursion: return node if it's p/q, recurse on both children, if both return non-null then current is LCA, otherwise propagate non-null one up. Return value has THREE meanings: LCA, one of p/q, or null.
⚡ Quick Implementation
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode() {}
TreeNode(int val) { this.val = val; }
TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
public static TreeNode buildTree(Integer[] arr) {
if (arr == null || arr.length == 0 || arr[0] == null) {
return null;
}
TreeNode root = new TreeNode(arr[0]);
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
int i = 1;
while (!queue.isEmpty() && i < arr.length) {
TreeNode current = queue.poll();
// Process left child
if (i < arr.length) {
if (arr[i] != null) {
current.left = new TreeNode(arr[i]);
queue.offer(current.left);
}
i++;
}
// Process right child
if (i < arr.length) {
if (arr[i] != null) {
current.right = new TreeNode(arr[i]);
queue.offer(current.right);
}
i++;
}
}
return root;
}
public static void print(TreeNode root) {
if (root == null) {
System.out.println("[]");
return;
}
List<String> result = new ArrayList<>();
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
TreeNode node = queue.poll();
if (node != null) {
result.add(String.valueOf(node.val));
queue.offer(node.left);
queue.offer(node.right);
} else {
result.add("null");
}
}
while (!result.isEmpty() && result.get(result.size() - 1).equals("null")) {
result.remove(result.size() - 1);
}
System.out.println(result);
}
}
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
// base case
if(root == null) {
return root;
}
// If current node itself is what we are searching for.
if(root.val == p.val || root.val == q.val) {
return root;
}
// Check p and q if exist in LST.
TreeNode left = lowestCommonAncestor(root.left, p, q);
// Check p and q if exist in RST.
TreeNode right = lowestCommonAncestor(root.right, p, q);
if(left != null && right != null) {
// means p and q are in different subtrees (LST and RST) of current root
return root;
} else if(left != null) {
return left;
} else if(right != null) {
return right;
}
return null;
}
public static void main(String[] args) {
Solution s = new Solution();
System.out.println(s.lowestCommonAncestor(TreeNode.buildTree(new Integer[] {3,5,1,6,2,0,8,null,null,7,4}), new TreeNode(5), new TreeNode(1) ).val); // 3
System.out.println(s.lowestCommonAncestor(TreeNode.buildTree(new Integer[] {3,5,1,6,2,0,8,null,null,7,4}), new TreeNode(5), new TreeNode(4) ).val); // 5
}
}
🔑 Key Insights
Return Value Semantics:
What each node returns:
1. If LCA found in subtree:
→ Return LCA
2. If only p or q found in subtree:
→ Return that node
3. If neither found in subtree:
→ Return null
Parent uses returns to decide:
Both non-null → Parent is LCA
One non-null → Propagate that one
Both null → Propagate null
Triple meaning is the KEY! 🔑
The Split Point:
LCA is where paths diverge:
3 ← LCA (split point)
/ \
5 1
(p here) (q here)
If both children return non-null:
One found p, other found q
Current node is where they split
Current IS the LCA! ✓
Visual: LCA = fork in the road! 🍴
Early Return Correctness:
When we find p or q, return immediately:
if (root == p || root == q) {
return root; // Don't explore children!
}
This is CORRECT because:
Case 1: This node is the LCA
(Other node is descendant)
→ Correct! We return LCA ✓
Case 2: LCA is ancestor of this
→ Parent will see our return
→ Will combine with other side
→ Correctly finds LCA ✓
Early return = optimization + correctness! ⚡
Node as Own Ancestor:
Example: LCA(5, 4) where 4 is child of 5
5* ← This is the LCA!
/
4*
When we reach 5:
return 5 (found!)
When we explore below 5:
Eventually find 4
Parent of 5 sees:
left = 5 (or wherever 5 is)
right = something or null
If 4 found below 5:
5 already returned itself
Algorithm handles correctly! ✓
No special case needed! 🎯
🎪 Memory Aid
"Return found node immediately!"
"Both non-null? Current is LCA!"
"One non-null? Propagate it up!"
"Triple meaning return value!" ✨
⚠️ Don't Forget
- Return immediately when found p or q!
- Check both non-null for LCA decision!
- Return value has 3 meanings (LCA/node/null)!
- Node can be own ancestor (handled naturally!)
- Post-order traversal (children before parent!)
- Single pass sufficient (elegant!)
🎉 Congratulations!
You've mastered one of the most elegant tree algorithms!
What You Learned:
✅ LCA concept - Lowest common ancestor
✅ Smart returns - Triple meaning
✅ Split point logic - Where paths diverge
✅ Early returns - Optimization + correctness
✅ Post-order decision - Based on children
✅ Single pass - Elegant solution
The Elegance:
This algorithm is BEAUTIFUL because:
1. Simple code (~10 lines)
2. Single pass through tree
3. Natural recursion
4. No extra data structures
5. Handles all edge cases
6. Returns have multiple meanings
Elegance = doing more with less! ✨
Interview Mastery:
Interviewer: "Find lowest common ancestor"
Your response:
"Use recursive DFS with smart returns.
Key insight: Return value has triple meaning:
1. LCA if both found in subtree
2. p or q if only one found
3. null if neither found
At each node:
- If current is p or q: return it
- Recurse on both children
- If both return non-null: current is LCA
- Otherwise: propagate non-null one up
Time: O(n), Space: O(h)"
Shows algorithm mastery! 💯
You've learned an algorithm that's used in countless real systems! 🏆✨🎯