← Back to DSA Animator
Lowest Common Ancestor of a Binary Tree LC #236 Medium DFS · Return-Value Propagation
Problem

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 the tree that has both p and q as descendants (a node can be a descendant of itself).

Example 1
Input: root = [3,5,1,6,2,0,8,null,null,7,4], p=5, q=1
Output: 3
Explanation: Node 3 is the LCA of nodes 5 and 1 — they are in different subtrees of 3.
Example 2
Input: root = [3,5,1,6,2,0,8,null,null,7,4], p=5, q=4
Output: 5
Explanation: Node 5 is itself an ancestor of node 4, so 5 is the LCA.
Constraints: 2 ≤ nodes ≤ 105  |  −109 ≤ Node.val ≤ 109  |  p ≠ q, both exist in the tree
Try Examples
Custom:
Approach
DFS Post-order: Return p/q When Found
Post-order DFS: after recursing both subtrees, if both left AND right returned non-null, this node is the LCA. If only one side returned non-null, propagate it up. The first node where both sides are non-null is the answer.
LCA Finder
p = ?
and
q = ?
Found p? searching...
Found q? searching...
LCA = ?
Binary Tree
Processing
Found p
Found q
LCA
Visited
DFS Call Stack
Stack is empty — not started
Variables
Current Node
—
left result
—
right result
—
LCA
—
Step Logic
Press ▶ Play or Next Step to begin the animation.
🎉
Ready
0 / 0
Select an example above and press Play.
Algorithm
1
Base: root==null → return null; root==p or root==q → return root
2
Recurse left: left = lca(root.left, p, q)
3
Recurse right: right = lca(root.right, p, q)
4
If left != null && right != null → return root (THIS is LCA!)
5
Else return whichever side is non-null (propagate up)
Time
O(n)
Space
O(h)
Why Return-Value Propagation Works

Each call returns the "found" node if it found p or q (or their ancestor), or null if neither was found. At any node: if both left and right calls returned non-null, it means p is in one subtree and q is in the other — so this node is the LCA. If only one side is non-null, that side already contains both targets (one is an ancestor of the other), so we propagate that result upward.