Lowest Common Ancestor of a Binary Tree
Problem statement
You are given the root of a binary tree and two of its nodes, p and q. Return their lowest common ancestor: the deepest node in the tree that has both p and q as descendants, where a node counts as its own descendant.
This is the general version of the question — the tree is not assumed to be a binary search tree, so you cannot use value comparisons to decide which way to go. Think of it as finding the closest shared manager of two employees in an org chart, where "closest shared manager" also allows one of them to be the other's manager.
Examples
Example 1
Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
Output: 3
Explanation: 5 and 1 are in different subtrees of the root (5 under the left child, 1 is the right child), so the root itself, 3, is their lowest common ancestor.

Example 2
Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
Output: 5
Explanation: 4 sits under node 2, which sits under node 5. Since a node can be its own ancestor, 5 is the lowest common ancestor of 5 and 4.

Hints
p, and the full path down to q, how would you find the last node the two paths have in common?Approach
Optimal: Single recursive pass
Intuition
A single recursive call, given a subtree, can answer one question: does this subtree contain p, q, both, or neither — and if it finds one of the targets directly, or both targets in different children, that is enough to identify the LCA without ever building a path or a parent map. If the current node is empty, or is p or q itself, return it immediately — no need to search deeper below a target you've already found. Otherwise, ask the same question of the left and right subtrees. If both come back non-empty, p and q were found in different subtrees, which makes the current node their lowest common ancestor. If only one side found something, pass that result up unchanged — the LCA must be higher up, on the side that actually contains both targets.
Steps
- If the current node is
null, or isp, or isq, return it as-is (this is the base case). - Recurse into the left subtree and the right subtree, getting back whatever each one found.
- If both recursive calls returned a non-null node,
pandqwere found on different sides of the current node — return the current node as the LCA. - Otherwise, return whichever side returned something non-null (or
nullif neither did) — this passes the answer up if it's already been found, or reports "not found here" if neither target is below.
Dry run
Finding LCA of 5 and 4 (tree: 3 → left 5 → left 6, right 2 → left 7, right 4; 3 → right 1):
| call | left result | right result | returns |
|---|---|---|---|
| visit(6) | — | — | null (neither target) |
| visit(7) | — | — | null |
| visit(4) | — | — | 4 (it is q) |
| visit(2) | left=visit(7)=null | right=visit(4)=4 | 4 (only one side non-null) |
| visit(5) | left=visit(6)=null | right=visit(2)=4 | 5 (5 is p, matched immediately at the base case before recursing) |
Node 5 is returned at its own call because the base case catches it directly (root is p) before it ever looks at its children — so visit(5) never actually needs the result from visit(2) to know the answer is 5 itself. The recursion above 5 (at node 3) then receives 5 from the left and null from the right (since 1's subtree holds neither target), so 3 passes 5 straight up, and the top-level call returns 5 — matching the expected output.
Edge cases: if p is itself an ancestor of q, the recursion hits p's base case first (return p immediately, without searching p's own subtree for q), so p correctly comes back as the answer without ever needing to confirm that q is really underneath it.
Complexity
Time O(n) - Every node is visited exactly once by the recursion, with O(1) work done at each node beyond the recursive calls themselves.
Space O(h) - Only the recursion's call stack is used, one frame per node on the current root-to-leaf path, so O(log n) for a balanced tree and up to O(n) for a skewed one.
class Solution:
def lowestCommonAncestor(
self, root: "TreeNode", p: "TreeNode", q: "TreeNode"
) -> "TreeNode":
if root is None 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 if left else right
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def build_tree(values):
from collections import deque
if not values or values[0] is None:
return None
root = TreeNode(values[0])
queue = deque([root])
i = 1
n = len(values)
while queue and i < n:
node = queue.popleft()
if i < n:
v = values[i]
i += 1
if v is not None:
node.left = TreeNode(v)
queue.append(node.left)
if i < n:
v = values[i]
i += 1
if v is not None:
node.right = TreeNode(v)
queue.append(node.right)
return root
def find_node(root, val):
if root is None:
return None
if root.val == val:
return root
return find_node(root.left, val) or find_node(root.right, val)
if __name__ == "__main__":
values = [3, 5, 1, 6, 2, 0, 8, None, None, 7, 4]
root1 = build_tree(values)
p1, q1 = find_node(root1, 5), find_node(root1, 1)
print(Solution().lowestCommonAncestor(root1, p1, q1).val) # 3
root2 = build_tree(values)
p2, q2 = find_node(root2, 5), find_node(root2, 4)
print(Solution().lowestCommonAncestor(root2, p2, q2).val) # 5RecapThe whole problem in a few lines, for the night before
- Spot it: "find the closest node that is an ancestor of both p and q" in a plain binary tree — no ordering property to exploit, unlike a BST
- Idea: a node is the LCA once p and q are found on different sides of it (or the node is one of them itself); a single recursive pass can detect this by checking whether both its left and right calls came back non-null
- Cost: O(n) time in every approach; O(h) space for the recursive or path-based versions, O(n) space for the parent-map version
- Trap: assuming the tree is a BST and comparing values to pick a direction — this problem gives no ordering guarantee, so that shortcut can silently return the wrong node
Interview follow-ups
The tree keeps a parent pointer on every node already, and you're allowed to call it. Does that change your approach?
Yes — with parent pointers already available, you can skip the pointer-building traversal entirely and go straight to the "walk up from
p, collect its ancestors, then walk up fromquntil you hit one" logic from the Better approach. This drops the time to just the two upward walks, O(h) each, since no O(n) pass over the tree is needed to construct the parent map first.You need to answer many LCA queries on the same fixed tree, not just one. How would you avoid repeating O(n) work each time?
Preprocess the tree once — for example, compute an Euler tour with node depths and build a sparse table (or another range-minimum-query structure) over it, which takes O(n log n) time and space up front. Each individual query then reduces to a range-minimum lookup, answered in O(1) or O(log n) time depending on the structure chosen, instead of re-walking O(n) or O(h) of the tree for every pair asked about.
Frequently asked questions
Because the tree here is a plain binary tree with no ordering guarantee between a node and its children, so there is no rule like "smaller values go left" to steer the search. The only structural fact available is parent-child membership, which is why every approach here relies on tracking ancestry directly — through explicit paths, a parent map, or the recursion's own call stack — rather than comparing values to decide direction.
Because that check happens implicitly through the recursion's base case and its two-sided return. If a node's left subtree returns non-null and its right subtree also returns non-null, that already proves one target is on each side — nothing needs to explicitly confirm which target is where. If a target is found directly (the current node equals p or q), the function stops descending into that node's own subtree, because a node is allowed to be its own ancestor, so nothing further below it needs to be found.
The same shape shows up whenever you need the "closest shared point" between two locations in a hierarchy: the nearest common parent module in a build dependency tree, the closest shared owner in a Kubernetes ownership chain, or the point where two service call chains in a request trace diverged from a common caller.
With a BST, you can skip explicit search entirely: starting at the root, if both p and q have values less than the current node, go left; if both are greater, go right; the first node where they split (or where the current node equals one of them) is the LCA. That approach is O(h) time and O(1) extra space, faster than any approach here, but it depends entirely on the ordering property that a general binary tree does not have.
This problem guarantees both nodes exist, so none of the approaches here check for that case. Handling it would mean confirming both nodes were actually found (for example, having the recursive approach also return an explicit "found count," or checking that both entries exist in the parent map before proceeding) and returning null if either search comes up empty, since a common ancestor cannot exist for a node that isn't in the tree at all.
