[Medium] 236. Lowest Common Ancestor of a Binary Tree

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).”

Thinking Process

1. Post-order Traversal: Process children before parent to find LCA bottom-up
   • Return node if it matches target
   • Return current node if both subtrees found targets
   • Otherwise, propagate the found result upward

• Trees have no cycles — recursion is natural.
• Combine results from left and right subtrees at each node.
• Base case is usually null; height drives stack space.

Common Approaches

Typical techniques for this pattern:

Approach	Time	Space	Notes
Recursive DFS (this problem)	O(n)	O(h) stack	Natural for trees and graphs
Iterative DFS (stack)	O(n)	O(n)	Avoid recursion depth limits
DFS with memoization	O(n)	O(n)	Overlapping subproblems on graphs
Backtracking DFS	O(2^n) typical	O(n)	Enumerate choices with pruning

Examples

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.

Tree structure:
        3
       / \
      5   1
     / \ / \
    6  2 0  8
      / \
     7   4

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 1 is 5 (a node can be a descendant of itself).

Tree structure:
        3
       / \
      5   1
     / \ / \
    6  2 0  8
      / \
     7   4

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.

Common Mistakes

1. One node is ancestor of other: p = 5, q = 4 → return 5
2. Root is LCA: p and q in different subtrees → return root
3. Both nodes in same subtree: LCA is deeper in that subtree
4. Root equals one target: Return root

5. Skewed tree: Works correctly but O(n) space

6. Wrong traversal order: Using pre-order instead of post-order

   // WRONG:
   if (node == p || node == q) return node; // Check before recursion
   // ❌ May return too early
   

7. Not handling self as descendant: Forgetting that a node can be its own descendant
8. Wrong return logic: Returning null when one subtree found a match

   // WRONG:
   if (left && right) return node;
   return nullptr; // ❌ Should return left or right
   

9. Comparing values instead of nodes: Using node->val instead of node == p
10. Not propagating results: Not returning the found node from subtrees

Related Problems

• LC 236: Lowest Common Ancestor of a Binary Tree - This problem
• LC 235: Lowest Common Ancestor of a Binary Search Tree - BST version (easier)
• LC 1644: Lowest Common Ancestor of a Binary Tree II - Nodes may not exist
• LC 1650: Lowest Common Ancestor of a Binary Tree III - Nodes have parent pointers
• LC 1123: Lowest Common Ancestor of Deepest Leaves - LCA of deepest leaves
• LC 102: Binary Tree Level Order Traversal - Level-order traversal

Key Takeaways

1. Post-order Traversal: Process children before parent to find LCA bottom-up
2. Return Strategy:
   • Return node if it matches target
   • Return current node if both subtrees found targets
   • Otherwise, propagate the found result upward
3. Self as Descendant: If p is ancestor of q, return p (and vice versa)
4. Single Pass: Can find LCA in one traversal without storing paths

References

• LC 236: Lowest Common Ancestor of a Binary Tree on LeetCode
• LeetCode Discuss — LC 236: Lowest Common Ancestor of a Binary Tree
• LeetCode Editorial (may require premium)

Template Reference

• Trees