Lowest Common Ancestor of Binary Tree
Find the lowest node that has both p and q in its subtree (a node counts as its own ancestor).
Intuition
Ask each subtree: 'do you contain p or q?' If both children answer yes, the current node is the split point — the LCA. If only one does, the LCA lives on that side. The recursion returns whichever of p/q/LCA it finds.
This is the template for "ask both subtrees, then decide here" — post-order recursion. You'll reach for it whenever a node's answer needs results from below rather than context from above. The return value does double duty: it means found one of the targets on the way up, and found the LCA once both sides report back. When a single recursive function has to carry two meanings like that, post-order is usually why it works.
Approach
Return what you find
lca(node): None if empty; node itself if it is p or q; else combine child results.
Both sides answer → split point
left and right both non-None means p and q are in different subtrees — node is the answer, and it propagates unchanged upward.
One side answers → forward it
The non-None side already holds either the LCA or the single found target (correct when one target is the other's ancestor).
Solution & live demo
Common pitfalls
Comparing values instead of identity
if root.val == p.val or root.val == q.val:
if root is p or root is q:
The problem hands you node references, and general binary trees may repeat values — matching on val can latch onto a different node that merely looks the same. Identity is what was actually asked about.
Returning early when only one side is non-null
left = self.lowestCommonAncestor(root.left, p, q) if left: return left
left = self.lowestCommonAncestor(root.left, p, q) right = self.lowestCommonAncestor(root.right, p, q) if left and right: return root
Short-circuiting skips the right subtree entirely, so the case where the two targets are split across the children — the only case that makes the current node the LCA — is never detected. You'd return the first target found instead of the ancestor. Both sides must be evaluated before deciding.
Checking for the targets after recursing
left = ... right = ... if root is p or root is q: return root
if not root or root is p or root is q:
return rootWhen one target is an ancestor of the other, the answer is the higher node — and stopping there is what produces it. Recursing first lets the deeper target be returned past its own ancestor.
Edge cases
Recursion stops at p without exploring below — p returns as its own LCA, correct by the definition.
Only that child returns non-None; the answer bubbles from within it.