← DSA Atlas
Dedicated problem page · #236

Lowest Common Ancestor of a Binary Tree

MediumTrees and Binary Search TreesBottom-up LCA searchPost-order DFS returning found targets
Solve on LeetCode ↗
236
MediumTrees and Binary Search TreesPost-order DFS returning found targetsBottom-up LCA search

Lowest Common Ancestor of a Binary Tree

Given the root of a binary tree and two distinct nodes p and q that both exist in the tree, return their lowest common ancestor: the deepest node that has both p and q as descendants (a node may be a descendant of itself).

Open official problem prompt ↗
In plain English

Find the deepest node that sits above both target nodes on their root-to-node paths.

Picture it like this

Like tracing two people's ancestry back through a family tree until you reach the most recent common grandparent — the first shared name going upward.

Example
Input
root = [3, 5, 1, 6, 2, 0, 8, null, null, 7, 4], p = 5, q = 1
Output
3
Why
5 is in the left subtree of 3 and 1 is in the right subtree, so their deepest shared ancestor is the root 3.
Constraints
The number of nodes is in the range [2, 10^5]-10^9 <= Node.val <= 10^9All Node.val are uniquep != q and both p and q exist in the tree
Pattern lesson

See the pattern, then code

Bottom-up LCA search
Recognition clue

You need the deepest node from which both targets are reachable — a signal to bubble 'found' signals up from the leaves and detect where the two paths meet.

↗
Trees and Binary Search Trees

Hierarchies, subtree aggregation, path properties, or ordered tree queries.. If one target appears in a node's left subtree and the other in its right subtree, that node is the meeting point; a node that is itself a target and finds the other below it is also the answer.

New words, made simpleKnow these before the algorithm
Lowest common ancestor
The deepest node that has both p and q in its subtree.
Descendant of itself
A node counts as its own ancestor, so if p is an ancestor of q, the answer is p.
Post-order return
Combining child results at the parent after both recursions finish.
Approaches from first idea to best ideaCompare the trade-offs
ApproachHow it thinksCost
Store parent pointers

Correct but needs extra maps and two passes.

BFS/DFS to map each node to its parent, walk p's ancestors into a set, then climb from q until a match.

Time O(n)Space O(n)
Best choiceSingle recursive DFS

One pass, no auxiliary structures; the canonical solution.

Return p or q on contact and let the node where left and right both return non-null be the answer.

Time O(n)Space O(h)
The rule we keep true

Invariant

Each call returns a target node if exactly one target lies in its subtree, or the LCA if both do, or null if neither is present.

Why this is correct

Reasoning

The first node (deepest, since recursion returns bottom-up) that sees a target coming from both children must be the split point of the two paths, hence the lowest common ancestor. If a target itself is an ancestor of the other, the early return surfaces it as the meeting node.

The algorithm in three movesSay these aloud before coding
1Return the node if it is null, equal to p, or equal to q

left of 3 finds 5

2Recurse into the left subtree

right of 3 finds 1

3Recurse into the right subtree

both non-null -> LCA = 3

4If both sides return non-null, the current node is the LCA

5Otherwise return whichever side is non-null

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example
30
51
12
63
24
05
86
1 · Readnode 5 == p
2 · AskIs this a target?
3 · Update stateyes
4 · Resultreturn node 5 up to root's left
Key takeaway

Target 5 surfaces from the left, target 1 from the right; they meet at root 3.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

  1. 1
    Lines 9-10Base / hit

    Stop when off the tree or when a target is found, returning that node upward.

  2. 2
    Lines 11-12Search both subtrees

    Gather what each side found; each returns a target, an LCA, or null.

  3. 3
    Lines 13-15Decide

    Non-null from both sides means the split is here; otherwise pass up the one non-null result.

Make it stick

Edge cases, mistakes, and one self-check

E

Edge cases to test

  • p is an ancestor of q (or vice versa) — the ancestor is returned via the early hit
  • Targets in opposite subtrees of the root — root is the answer
  • Both targets always exist, so a null overall result cannot happen per constraints
!

Common beginner mistakes

  • Comparing by value instead of node identity when duplicates could exist (here values are unique, but identity comparison is safest)
  • Continuing to search after finding a target, missing the ancestor-of case
  • Returning True/False flags instead of the actual node, losing the answer
Check your understanding

Why is the first node where both recursive calls return non-null guaranteed to be the lowest common ancestor and not some higher one?

More in Trees and Binary Search Trees

#104Maximum Depth of Binary TreePost-order height aggregation#543Diameter of Binary TreePost-order height with a running best#102Binary Tree Level Order TraversalLevel-by-level BFS#98Validate Binary Search TreeRange-bounded validation#105Construct Binary Tree from Preorder and InorderPreorder root + inorder split#124Binary Tree Maximum Path SumPost-order gain with global best