Lowest Common Ancestor in Binary Tree
Find the lowest node that is ancestor of both p and q using recursive signal propagation.
Key concepts at a glance — for those who already know the basics.
Problem Statement
Lowest Common Ancestor of a Binary Tree
Return the lowest node in the tree that has both p and q as descendants. A node can be a descendant of itself, so ancestor cases are valid answers.
Core Rule: both sides non-null -> current node is LCA.
Intuition
Base hit
If node is null, p, or q, return immediately as recursion signal.
Signal merge
Collect left and right return values, then combine at parent.
Split point
The first node getting both signals is the lowest common ancestor.
Diagram
Split Case - LCA = 3
Ancestor Case - LCA = 5
Dry Run
| Call | Left | Right | Return |
|---|---|---|---|
| lca(5) | - | - | 5 |
| lca(1) | - | - | 1 |
| lca(3) | 5 | 1 | 3 (LCA) |
| lca(4) | - | - | 4 |
| lca(5,4 case) | 6 | 4 | 5 (LCA) |
Complexity
Time Complexity
O(n)
Each node is visited once.
Space Complexity
O(h)
Recursion stack depth, where h is tree height.
Interview tip: Explain split case and ancestor case before coding.
Ready to see it in action?
Step through the visualizer to watch the algorithm state update live.