DSA problem
Lowest Common Ancestor of a Binary Tree
Given a binary tree, find the lowest common ancestor (LCA) of two given nodes p and q in the tree. The LCA is defined as the lowest node in the tree that has both p and q as descendants (where we allow a node to be a descendant of itself). It is guaranteed that both p and q exist in the tree.
This is one of the most elegant post-order recursions in all of tree algorithms. The idea: a recursive call lca(node, p, q) returns something interesting — either p, q, the actual LCA, or null — by combining the answers from its two children. The combination rule is simple, and once it clicks the entire algorithm fits in five lines of code.
Here is the rule: if node itself is p or q, return node (we have found one of the targets and signal it upward). Otherwise recurse into both children. If both the left and right recursive calls return non-null, then node must be the LCA — one target is in its left subtree and the other in its right. If only one side is non-null, propagate that value upward; either it is one of the targets that the other target's call will meet at a higher ancestor, or it is the LCA already determined deeper down.
The algorithm runs in O(n) time (each node visited once) with O(h) recursion space. It does not require building a parent map, computing depths, or doing two separate traversals — the post-order structure naturally encodes "found p", "found q", and "found the meeting point" into the same return type.
Examples
root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 13root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 45root = [1,2], p = 1, q = 21Constraints
- The number of nodes in the tree is in the range [2, 10^5].
- -10^9 <= Node.val <= 10^9
- All Node.val are unique.
- p != q and both p and q exist in the tree.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.