Lowest Common Ancestor (LCA) — Complete LeetCode Guide

The Lowest Common Ancestor problem sits in Meta's top 10 most-asked questions, appears on the Blind 75, and comes up at Google, Amazon, and Microsoft in backend, frontend, and SWE generalist loops alike. It is one of those rare interview problems that tests multiple skills simultaneously: recursion fluency, tree traversal intuition, and the ability to handle edge cases cleanly. Candidates who have studied LCA can dispatch the base problem in under five minutes. Candidates who have not will often spiral into overly complex iterative solutions that fail on the "p is an ancestor of q" edge case.

LCA is not a single problem — it is a family. LeetCode #236 (Binary Tree) and #235 (Binary Search Tree) are the canonical entry points, but interviewers increasingly reach for #1650 (nodes with parent pointers) and #1123 (LCA of deepest leaves) as follow-ups. Understanding the pattern family — not just the recursive trick — is what separates confident LCA answers from fragile ones.

This guide walks through every major LCA variant in order of increasing complexity. You will learn the recursive insight that makes #236 trivial, how the BST property reduces #235 to a one-liner loop, how parent pointers turn the problem into a linked-list intersection problem, and how deepest leaves adds a depth-tracking dimension. Along the way we cover every edge case that traps candidates under pressure, with clear mental models for each.

The Lowest Common Ancestor of two nodes p and q in a tree is defined as the deepest node that has both p and q as descendants, where a node is considered a descendant of itself. That last clause — a node is a descendant of itself — is critical and is the source of the most common LCA edge case: when p is an ancestor of q (or vice versa), the LCA is p itself, not some higher ancestor.

Visually: in a tree with root 3, left child 5, right child 1, and 5's children being 6 and 2 — the LCA of nodes 5 and 1 is 3 (the root). The LCA of nodes 5 and 6 is 5 (because 5 is an ancestor of 6, and the definition includes self-ancestry). The LCA of nodes 6 and 2 is 5 (their immediate parent). Internalizing these three cases — both in different subtrees, one is ancestor of the other, immediate siblings — covers the vast majority of what interviewers probe.

Real-world analogues make LCA memorable: in version control (git), the LCA of two branches is their merge base — the most recent common commit. In org charts, the LCA of two employees is their closest shared manager. In file systems, the LCA of two paths is their longest common directory prefix. These analogues reinforce why LCA is so broadly useful and why it appears in system design discussions as well as algorithm rounds.

The three primary LeetCode LCA problems are: #235 (LCA of a Binary Search Tree, Easy), #236 (LCA of a Binary Tree, Medium), and #1650 (LCA of a Binary Tree III — nodes with parent pointers, Medium). Secondary variants include #1123 (LCA of Deepest Leaves, Medium) and less commonly tested DAG and multi-node LCA problems. This guide covers all four primary problems in detail.

LCA of a Binary Search Tree (#235) is rated Easy on LeetCode, and it earns that rating once you internalize the BST ordering property. In a BST, every node in the left subtree is smaller than the root, and every node in the right subtree is larger. This gives you a free navigation signal at every node: if both p and q are less than the current node, the LCA must be in the left subtree. If both are greater, the LCA must be in the right subtree. If they split — one less, one greater, or one equals the current node — the current node is the LCA.

The iterative implementation is as clean as it gets: start at root, loop while root is not null. If both p.val and q.val are less than root.val, move left. If both are greater, move right. Otherwise return root. No recursion needed, no auxiliary data structures, O(h) time where h is the height of the tree (O(log n) for balanced BSTs, O(n) worst case for skewed trees). This is the solution interviewers expect — clean, exploiting the BST property, no wasted work.

The BST LCA also handles the self-ancestor edge case automatically: if p.val == root.val or q.val == root.val, neither the left nor right branch condition is triggered, and the current root is returned — which is correct, since a node is its own ancestor. A common follow-up question is: 'What if this were a general binary tree instead of a BST?' — that is exactly #236, and the answer requires a fundamentally different approach because you can no longer navigate directionally.

The Lowest Common Ancestor in a BST (#235) runs in O(h) time — O(log n) for balanced trees — by exploiting the BST ordering property. This is a common follow-up question in interviews: interviewers will ask you to implement BST LCA first, then escalate to general binary tree LCA to see if you understand why the BST shortcut disappears.

LCA of a Binary Tree (#236) is the canonical LCA problem and the one most interviewers mean when they say 'LCA problem'. Unlike the BST variant, a general binary tree gives you no ordering property to navigate with — you cannot tell from a node's value whether p and q are in the left subtree, right subtree, or split across both. The solution requires a full recursive traversal.

The recursive insight is the key to understanding LCA: at any node, recursively ask 'does my left subtree contain p or q?' and 'does my right subtree contain p or q?' If both return non-null results — meaning p was found in the left subtree and q in the right (or vice versa) — then the current node is the LCA, because this is the lowest point at which the paths to p and q diverge. If only one side returns non-null, propagate that result upward — it means both p and q are in the same subtree.

The base cases handle two critical scenarios elegantly: if the current node is null, return null (we have gone past a leaf without finding either node). If the current node is p or q, return it immediately — this handles both the 'found a target' case and the self-ancestor edge case in one line. When p is an ancestor of q, the recursion will find p first and return it before ever reaching q. The caller receives a non-null result from one subtree and null from the other, so it propagates p upward. At no point does the self-ancestor case need special handling.

The Lowest Common Ancestor of a Binary Tree (#236) is solved in O(n) time with a single recursive pass — the key insight is that if a node's left subtree contains p and right subtree contains q, that node must be the LCA. This single-pass property is what makes the solution so elegant: there is no preprocessing, no parent pointer construction, no hash set of ancestors — just a clean postorder traversal where the answer bubbles up naturally.

Space complexity is O(h) for the call stack — O(log n) for balanced trees, O(n) for skewed. In an interview, always state both time and space complexity. The O(n) time bound is tight: in the worst case (p and q are leaves in opposite subtrees), every node is visited exactly once.

LCA of a Binary Tree III (#1650) gives you nodes with parent pointers — each node has a val, left child, right child, and parent pointer. The LCA question is the same, but the parent pointer changes the optimal approach entirely. The BST and binary tree recursive approaches both traverse top-down from the root. With parent pointers, you can traverse bottom-up from p and q toward the root, which opens up the classic 'two-pointer linked list intersection' approach.

For #1650, the cleanest solution: collect all ancestors of p into a hash set by walking p's parent chain to the root. Then walk q's parent chain upward — the first ancestor of q that appears in p's ancestor set is the LCA. Time O(h), space O(h). An alternative that achieves O(h) time with O(1) space mirrors the linked list cycle detection trick: two pointers starting at p and q, each advancing to parent (and when reaching null, jumping to the other node's start). They meet at the LCA for the same reason the two-pointer approach finds the intersection of two linked lists.

LCA of Deepest Leaves (#1123) asks for the LCA of all the deepest nodes in the tree — not a specific pair, but whichever nodes are at the maximum depth. The approach combines depth tracking with LCA logic. A recursive helper returns a (node, depth) pair: for a leaf, return (leaf, depth). For an internal node, recursively get (leftLCA, leftDepth) and (rightLCA, rightDepth). If leftDepth == rightDepth, both subtrees reach the same maximum depth so the current node is the LCA of all deepest leaves. If one is deeper, return that subtree's LCA. This single-pass approach runs in O(n) time.

Multi-node LCA (finding the LCA of a list of k nodes, not just two) is an extension that sometimes appears in senior interviews or system design discussions. The recursive approach from #236 generalizes naturally: instead of checking root == p or root == q, check if root is in a set of target nodes. Instead of returning root when both subtrees return non-null, track the count of non-null returns — when the count reaches k (or reaches 2+, depending on the variant), the current node is the LCA of the full set.

The most common LCA mistake is missing the self-ancestor edge case: when p is an ancestor of q, the LCA is p, not the root or the node above p. Candidates who forget to return the current node early (when root == p or root == q) will traverse past p, find q in a subtree, and return a node that is deeper than the correct LCA. The fix is embedded in the standard recursive solution — the early return on root == p or root == q handles it automatically, but only if you include that check before the recursive calls, not after.

The second most common mistake: assuming p and q are always present in the tree. LeetCode #236 guarantees both nodes are in the tree, but follow-up variants may not. If either node might be absent, the recursive function needs to track how many target nodes were actually found. A clean way to handle this: return a (node, foundCount) pair instead of just a node. Only return the LCA candidate when foundCount == 2 (both nodes confirmed found).

Null handling in the recursive solution trips up candidates who try to write the logic bottom-up without first establishing the base cases. Always write the base cases first: null returns null, target node returns itself. Then the combine logic (both non-null → return root, else return non-null side) falls into place naturally. Reversing this order — writing the combine logic first and trying to bolt on base cases — produces convoluted conditionals.

One-sided trees (linked-list degenerate trees) are a space complexity trap. The O(h) stack space for the recursive solution becomes O(n) on a completely skewed tree. If an interviewer asks about space optimization, the response is to convert the recursive solution to an iterative postorder traversal using an explicit stack — same O(n) time, same O(h) worst-case stack space, but the explicit stack avoids call stack overflow on extremely deep trees in production code.

Confusing LCA with 'lowest common ancestor in a DAG' is a conceptual error that occasionally appears. In a DAG, a node can have multiple parents, so the LCA is not necessarily unique and the definition requires careful specification. For interview purposes, assume all LCA problems refer to trees (single parent per node) unless explicitly told otherwise. If a DAG variant appears, flag the ambiguity before answering.

The LCA problem family is deceptively narrow in appearance but remarkably rich in what it tests. The base problem (#236) tests recursive thinking and postorder traversal fluency. The BST variant (#235) tests whether you exploit problem-specific structure rather than applying a generic algorithm. The parent pointer variant (#1650) tests cross-domain pattern recognition — recognizing that a tree problem with parent pointers is structurally identical to linked list intersection. The deepest leaves variant (#1123) tests your ability to combine two orthogonal concerns (depth tracking and LCA logic) into a single clean recursive function.

What interviewers are actually evaluating across all LCA problems is the same skill: can you reason cleanly about recursive tree functions? Candidates who have internalized the LCA pattern can handle all four variants because they understand the core insight — return the current node when it is a target or when its two subtrees each contain a target — and can adapt that insight to new constraints without re-deriving from scratch.

The LCA problem is also a forcing function for interview fundamentals: state the definition and clarifying assumptions before coding, identify the base cases explicitly, derive the combine logic from the base cases, and verify on the three canonical edge cases (split subtrees, self-ancestor, identical nodes) before submitting. Candidates who demonstrate this structured approach — even on a problem they know well — signal strong engineering habits beyond just algorithm knowledge.

YeetCode's spaced repetition system is particularly effective for LCA because the problem family has multiple variants that are easy to conflate. Drilling #235, #236, #1650, and #1123 in rotation — with forced recall rather than passive re-reading — builds the mental discrimination that lets you immediately identify which variant is being asked and which approach to apply. The goal is not to memorize code but to reach the point where the recursive structure of each variant is immediately obvious, so you can spend interview time on clean implementation and edge case discussion rather than re-deriving the approach.