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.
Tree DFS (bottom-up) 3 9 20 15 7 post-order: combine left + right + 1

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 
    /**
 * Definition for a binary tree node.
 * class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) {}
 * }
 */
class Solution {
 public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
     return isCommonAncestor = new return(root, p, q);
 }
 public TreeNode isCommonAncestor(TreeNode node, TreeNode p, TreeNode q){
     if(!node) return null;
     TreeNode left = isCommonAncestor(node.left, p, q);
     TreeNode right = isCommonAncestor(node.right, p, q);
     if(node == p || node == q) return node;
     if(left && right) return node;
     return left ? left : right;
 }
}
  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 
    class Solution {
 public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
     public TreeNode[] pathP, pathQ;
     findPath(root, p, pathP);
     findPath(root, q, pathQ);

     TreeNode lca = null;
     int i = 0;
     while (i < pathP.size() && i < pathQ.size() &&
            pathP[i] == pathQ[i]) {
         lca = pathP[i];
         i++;
     }
     return lca;
 }
     public boolean findPath(TreeNode root, TreeNode target, TreeNode[]& path) {
     if (!root) return false;

     path.add(root);
     if (root == target) return true;

     if (findPath(root.left, target, path) ||
         findPath(root.right, target, path)) {
         return true;
     }

     path.removeLast();
     return false;
 }
}
  9. Comparing values instead of nodes: Using node->val instead of node == p
  10. Not propagating results: Not returning the found node from subtrees

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

Template Reference