Skip to main content

236 - Lowest Common Ancestor of a Binary Tree

Difficulty: Medium | Pattern: Tree DFS (Post-Order) | Company tags: Amazon, Google, Facebook, Microsoft, LinkedIn

Problem Statement​

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

The LCA is defined 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:

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

Input: root=[3,5,1,6,2,0,8,null,null,7,4], p=5, q=1
Output: 3

Example 2 (node is ancestor of the other):

Same tree, p=5, q=4
Output: 5 (5 is an ancestor of 4, so LCA is 5 itself)

Approach: Recursive Post-Order DFS​

Key insight: After recursively searching the left and right subtrees, at any node:

  • If both left and right returned a non-null result → this node is the LCA (p and q are in different subtrees)
  • If only one side returned non-null → that non-null value propagates up (either the node found is p or q which is an ancestor of the other, or it's the LCA we already found)
  • If neither side found anything and this node isn't p or q → return null
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def lowestCommonAncestor(root, p, q):
    # Base case: if this node is None, p, or q — return it
    if not root or root == p or root == q:
        return root
    
    left = lowestCommonAncestor(root.left, p, q)
    right = lowestCommonAncestor(root.right, p, q)
    
    # Both sides found something → this node is the LCA
    if left and right:
        return root
    
    # Only one side found something → propagate that up
    return left if left else right

Algorithm Flow​

Dry Run​

Tree above, p=5, q=1:

  • At node 3: recurse left and right
    • Left subtree (rooted at 5): found p=5 at node 5 → returns 5
    • Right subtree (rooted at 1): found q=1 at node 1 → returns 1
    • Both left=5 and right=1 non-null → return node 3 as LCA ✓

Tree above, p=5, q=4:

  • At node 5: 5 == p → return 5 immediately
  • At node 3: left=5 (non-null), right=null (1 and its subtree don't contain q=4)
  • Wait — actually: right subtree (1) → doesn't find 4 → returns null
  • left=5 non-null, right=null → return left = 5 ✓

Key Insight Explained​

The algorithm works because:

  1. When we reach p or q, we return it without going deeper — we've found one of the targets
  2. The first ancestor where both subtrees return non-null is the split point = LCA
  3. If one node is an ancestor of the other, the deeper one is never found before the LCA (the ancestor) returns itself

Complexity​

  • Time: O(n) — visits every node in the worst case
  • Space: O(h) — recursion stack where h = tree height; O(n) for skewed tree

Key Terms​

TermDefinition in this problem's context
Post-order DFSRecurse into left and right subtrees first, then use both results at the current node — necessary here because the LCA decision depends on what both children report.
Split pointThe node whose left and right recursive calls both return non-null — this is exactly where p and q diverge into different subtrees.
Result propagationWhen only one subtree finds a target, that result bubbles straight up unchanged through ancestors until it reaches the true split point or another match.
Self-ancestorA node is allowed to be its own ancestor, so if root == p or root == q, the function returns immediately without searching further down that branch.

FAQ​

  1. Can this be solved without extra space? Not really — the recursive DFS inherently uses O(h) call-stack space; an iterative version with explicit parent-pointer maps still needs O(n) auxiliary space to store parent chains.

  2. What if p or q doesn't exist in the tree? The base algorithm assumes both exist (per LeetCode's constraints) and may silently return an incorrect ancestor otherwise; a robust version would first verify both nodes are present via a full traversal.

  3. How would this differ if it were a BST instead of a general binary tree? You could skip searching both subtrees and instead use value comparisons to navigate directly toward the LCA in O(h) time — that's exactly LC 235's optimization.

  4. What's the follow-up interviewers usually ask? "What if each node has a parent pointer instead of just children?" — then you can find each node's path to root and treat it like finding the intersection of two linked lists, or walk both paths simultaneously.

  5. Does this handle the case where one node is an ancestor of the other? Yes — when the algorithm reaches the ancestor node first (say p), it returns immediately since root == p, and that result propagates up unchanged, correctly yielding p as the LCA without ever needing to locate the deeper node q explicitly beneath it.

Quick Revision​

  • Pattern: post-order DFS — process children before deciding the current node's role.
  • Base case: if root is None, p, or q, return root immediately.
  • Recurse into left and right subtrees independently.
  • If both left and right are non-null, the current node is the split point — return it as the LCA.
  • If only one side is non-null, propagate that result upward unchanged.
  • If neither side found anything, return None.
  • Handles the "ancestor of itself" case naturally: reaching p or q early causes it to propagate straight up if it's actually the LCA.
  • Time: O(n) — every node may be visited once.
  • Space: O(h) recursion stack, O(n) worst case for a skewed tree.
  • Contrast with LC 235 (BST version): exploits ordering for O(h) time and O(1) iterative space.