Given a binary tree and two nodes p and q, find their lowest common ancestor. That is the deepest node that has both p and q in its subtree, where a node counts as its own descendant.
DSA Animator › DSA Revision › Tree › Lowest Common Ancestor of a Binary Tree
Remember: when both sides report a find, the current node is the split point. A node can be its own ancestor, which is why returning p or q early is correct. The video solves Lowest Common Ancestor of a Binary Tree (LeetCode 236, Medium) with the Postorder DFS pattern from the Tree topic, and you can replay every step in the interactive Lowest Common Ancestor of a Binary Tree animation.
Given a binary tree and two nodes p and q, find their lowest common ancestor. That is the deepest node that has both p and q in its subtree, where a node counts as its own descendant.
In the tree 3, 5, 1, 6, 2, 0, 8, with 7 and 4 under 2, take p equal to 6 and q equal to 4. Both sit under 5, and 5 is the deepest such node, so the answer is 5.
You could store the path from the root to p and the path to q, and find where they split. That works, but it needs two extra lists and two searches. A single postorder search can report what it found to its parent.
Ask each subtree: did you find p or q? If the current node is null, p or q, return it straight away. Otherwise search the left and the right subtree. If both sides return something, then p and q are split across this node, so this node is the answer. If only one side returns something, pass that up.
Start at 3 and go into the left subtree, 5. From 5 go left to 6, which is p, so 6 is returned. From 5 go right to 2, then 7 returns null, and 4 is q, so 2 passes 4 up. At 5, the left side returned 6 and the right side returned 4. Both sides found something, so 5 is the lowest common ancestor. Back at 3, the right subtree 1 returns null, so 3 simply passes 5 up. The answer is 5.
In code, if root is null, p or q, return root. Recurse into left and right. If both results are not null, return root. Otherwise return whichever result is not null. Each node is visited once, so it's O of n time and O of the height in stack space.
Remember: when both sides report a find, the current node is the split point. A node can be its own ancestor, which is why returning p or q early is correct.