Lowest Common Ancestor of a Binary Tree: The Algorithm Behind LeetCode 236

You have a family tree. Two nodes are feuding over inheritance. Someone needs to find their most recent shared ancestor before things get complicated.

That's the lowest common ancestor problem. It shows up in LeetCode 236, 235, 1650, and 1676. The naive solution is something your college self would write at 2am. The elegant recursive one is seven lines that interviewers have been making candidates sweat over for two decades.

What "Ancestor" Actually Means

A node A is an ancestor of node B if A lies on the path from the root down to B. A node is also considered an ancestor of itself. That last part is not a typo.

Given this tree:

The ancestors of node 4 are: 2, 5, 3. The ancestors of node 6 are: 5, 3.

The lowest common ancestor of two nodes is the deepest node that is an ancestor of both. For nodes 4 and 6, that's node 5. For nodes 5 and 4, it's node 5 itself because 5 is an ancestor of 4, and a node counts as its own ancestor. The second case is the one that trips up most candidates mid-interview.

The Naive Approach

The obvious solution: find the path from root to p, find the path from root to q, then return the last node they share. This is what every engineer writes when they first see the problem. It's correct. Interviewers will nod politely and wait.

def find_path(root, target, path):
    if not root:
        return False
    path.append(root)
    if root is 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_naive(root, p, q):
    path_p, path_q = [], []
    find_path(root, p, path_p)
    find_path(root, q, path_q)
    last_common = None
    for a, b in zip(path_p, path_q):
        if a == b:
            last_common = a
        else:
            break
    return last_common

O(n) time and O(n) space. Two full traversals, two stored paths. It works. But you're leaving the elegant version unwritten, and interviewers know the elegant version exists.

Binary Tree LCA: The Recursive Insight Interviewers Test

The elegant solution visits each node exactly once. Each node returns upward what it found. If it found p or q, return that node. If it found both in different subtrees, return itself as the LCA. If it found nothing, return null.

def lowestCommonAncestor(root, p, q):
    if not root or root is p or root is q:
        return root
    left = lowestCommonAncestor(root.left, p, q)
    right = lowestCommonAncestor(root.right, p, q)
    if left and right:
        return root
    return left or right

Walk through p=4, q=6 on the tree above:

Node 6 matches q. Returns node 6.
Node 4 matches p. Returns node 4.
Node 5: left returned node 6, right returned node 4. Both non-null. Returns node 5.
Node 3: left returned node 5, right returned null. Returns node 5.

If both sides return non-null, the current node is the LCA. p and q can split across subtrees at exactly one node in the whole tree. That node is their LCA. Seven lines.

There's a tricky case worth tracing manually: what if p is an ancestor of q? Say p is node 5 and q is node 4. When recursion reaches node 5, line 2 fires: root is p, so it returns p immediately without recursing into p's subtree. The parent sees "left returned p, right returned null" and returns p. Correct. Remove the early return condition and the algorithm silently fails for this case. Half the test cases on LeetCode check exactly this.

Tom and Jerry debugging meme: Tom about to hit himself while Jerry (the bug) dodges Tracing the ancestor-of-itself case by hand the first time you see it.

The BST Shortcut

If the tree is a BST, you don't need to search blindly. The ordering property tells you exactly which direction to go.

def lowestCommonAncestor(root, p, q):
    if p.val < root.val and q.val < root.val:
        return lowestCommonAncestor(root.left, p, q)
    if p.val > root.val and q.val > root.val:
        return lowestCommonAncestor(root.right, p, q)
    return root

If both nodes are smaller than root, both live in the left subtree. If both are larger, recurse right. Otherwise root is the split point and is the LCA.

This runs in O(h) time: O(log n) for a balanced BST, O(n) worst case for a skewed one. The iterative version eliminates the call stack:

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

A BST LCA question is solvable with the generic binary tree version too. It just ignores a free win, and interviewers notice free wins left on the table.

Reading the Complexity

Approach	Time	Space
Naive (two path searches)	O(n)	O(n)
Recursive, binary tree	O(n)	O(h)
Recursive, BST	O(h)	O(h)
Iterative, BST	O(h)	O(1)

The recursive binary tree solution visits every node in the worst case. Space is O(h) for the call stack: O(log n) balanced, O(n) skewed.

A code snippet showing a "BIG-O ALGORITHMIC COMPLEXITY TRACKER" that measures complexity by counting indentation levels in the source code There are faster O(n) preprocessing approaches out there. This is not one of them.

Tarjan's offline algorithm (1979) achieves near-linear time with Union-Find. Bender and Farach-Colton (2000) reduced LCA to Range Minimum Query on an Euler tour, giving O(n) preprocessing and O(1) per query. Neither comes up in standard interviews. The seven-line recursive solution is the answer interviewers want.

The Problems You'll Actually See

LeetCode 236: Binary Tree LCA. The recursive solution above solves it directly.

LeetCode 235: BST LCA. Use the BST shortcut. Simpler because the ordering property does half the work for you.

LeetCode 1650: Binary Tree with parent pointers. Each node has a parent field. Treat it like two linked lists meeting at a node: find depths, align, walk upward together. O(h) time, O(1) space.

LeetCode 1676: LCA of multiple nodes. Store all targets in a set, change the base case to check set membership. The rest of the recursion is identical.

If you're prepping for a mock interview and want to practice explaining the recursive insight out loud before you code it, SpaceComplexity runs voice-based DSA sessions where an AI interviewer prompts you through exactly this kind of problem and scores how well you articulate the "both sides return non-null" moment.

One Structure, Every Language

The recursive binary tree solution (LeetCode 236) below. The core logic is identical across all 14 languages. What changes is how each language expresses null checks and boolean-style returns.

Python 3

def lowestCommonAncestor(root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
    if not root or root is p or root is q:
        return root
    left = lowestCommonAncestor(root.left, p, q)
    right = lowestCommonAncestor(root.right, p, q)
    if left and right:
        return root
    return left or right

Use is for identity comparison. LeetCode's TreeNode does not override __eq__, so == falls back to identity anyway, but is makes intent clear.

Python 2

def lowestCommonAncestor(self, root, p, q):
    if not root or root is p or root is q:
        return root
    left = self.lowestCommonAncestor(root.left, p, q)
    right = self.lowestCommonAncestor(root.right, p, q)
    if left and right:
        return root
    return left or right

JavaScript

function lowestCommonAncestor(root, p, q) {
    if (!root || root === p || root === q) return root;
    const left = lowestCommonAncestor(root.left, p, q);
    const right = lowestCommonAncestor(root.right, p, q);
    if (left && right) return root;
    return left || right;
}

TypeScript

function lowestCommonAncestor(
    root: TreeNode | null,
    p: TreeNode,
    q: TreeNode
): TreeNode | null {
    if (!root || root === p || root === q) return root;
    const left = lowestCommonAncestor(root.left, p, q);
    const right = lowestCommonAncestor(root.right, p, q);
    if (left && right) return root;
    return left || right;
}

Java

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    if (root == null || root == p || root == q) return root;
    TreeNode left = lowestCommonAncestor(root.left, p, q);
    TreeNode right = lowestCommonAncestor(root.right, p, q);
    if (left != null && right != null) return root;
    return left != null ? left : right;
}

Java has no || for objects, so the ternary handles "return whichever side is non-null."

C++

TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    if (!root || root == p || root == q) return root;
    TreeNode* left = lowestCommonAncestor(root->left, p, q);
    TreeNode* right = lowestCommonAncestor(root->right, p, q);
    if (left && right) return root;
    return left ? left : right;
}

struct TreeNode* lowestCommonAncestor(
    struct TreeNode* root,
    struct TreeNode* p,
    struct TreeNode* q
) {
    if (!root || root == p || root == q) return root;
    struct TreeNode* left = lowestCommonAncestor(root->left, p, q);
    struct TreeNode* right = lowestCommonAncestor(root->right, p, q);
    if (left && right) return root;
    return left ? left : right;
}

func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
    if root == nil || root == p || root == q {
        return root
    }
    left := lowestCommonAncestor(root.Left, p, q)
    right := lowestCommonAncestor(root.Right, p, q)
    if left != nil && right != nil {
        return root
    }
    if left != nil {
        return left
    }
    return right
}

Go has no ternary operator, so the final check splits into two if blocks.

Rust

Rust's Rc<RefCell<TreeNode>> wrapper is verbose. LeetCode guarantees unique node values, so comparing by val avoids the complexity of Rc::ptr_eq.

use std::cell::RefCell;
use std::rc::Rc;

fn lowest_common_ancestor(
    root: Option<Rc<RefCell<TreeNode>>>,
    p: Option<Rc<RefCell<TreeNode>>>,
    q: Option<Rc<RefCell<TreeNode>>>,
) -> Option<Rc<RefCell<TreeNode>>> {
    let root = root?;
    let p_val = p.as_ref().unwrap().borrow().val;
    let q_val = q.as_ref().unwrap().borrow().val;
    let root_val = root.borrow().val;
    if root_val == p_val || root_val == q_val {
        return Some(Rc::clone(&root));
    }
    let (left_child, right_child) = {
        let node = root.borrow();
        (node.left.clone(), node.right.clone())
    };
    let left = lowest_common_ancestor(left_child, p.clone(), q.clone());
    let right = lowest_common_ancestor(right_child, p, q);
    match (left, right) {
        (Some(_), Some(_)) => Some(root),
        (l, r) => l.or(r),
    }
}

The borrow scope is isolated to extract children before recursing, avoiding a borrow conflict across the recursive calls.

Swift

func lowestCommonAncestor(_ root: TreeNode?, _ p: TreeNode?, _ q: TreeNode?) -> TreeNode? {
    guard let root = root else { return nil }
    if root === p || root === q { return root }
    let left = lowestCommonAncestor(root.left, p, q)
    let right = lowestCommonAncestor(root.right, p, q)
    if left != nil && right != nil { return root }
    return left ?? right
}

Swift uses === for reference identity. The ?? nil-coalescing operator handles "return whichever is non-nil."

Kotlin

fun lowestCommonAncestor(root: TreeNode?, p: TreeNode?, q: TreeNode?): TreeNode? {
    if (root == null || root == p || root == q) return root
    val left = lowestCommonAncestor(root.left, p, q)
    val right = lowestCommonAncestor(root.right, p, q)
    if (left != null && right != null) return root
    return left ?: right
}

Kotlin's Elvis operator ?: replaces the ternary cleanly.

public TreeNode LowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    if (root == null || root == p || root == q) return root;
    TreeNode left = LowestCommonAncestor(root.left, p, q);
    TreeNode right = LowestCommonAncestor(root.right, p, q);
    if (left != null && right != null) return root;
    return left ?? right;
}

Ruby

def lowest_common_ancestor(root, p, q)
  return root if root.nil? || root == p || root == q
  left = lowest_common_ancestor(root.left, p, q)
  right = lowest_common_ancestor(root.right, p, q)
  return root if left && right
  left || right
end

Ruby's trailing if makes guard clauses read close to English.

PHP

function lowestCommonAncestor($root, $p, $q) {
    if ($root === null || $root === $p || $root === $q) return $root;
    $left = lowestCommonAncestor($root->left, $p, $q);
    $right = lowestCommonAncestor($root->right, $p, $q);
    if ($left !== null && $right !== null) return $root;
    return $left ?? $right;
}

Use === for strict identity in PHP. The ?? null coalescing operator is available since PHP 7.