LeetCode #236 Medium

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).

treedfsrecursion

02

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.

03

Approach

1

Return what you find

lca(node): None if empty; node itself if it is p or q; else combine child results.

2

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.

3

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).

04

Solution & live demo

python

▶1class Solution:
▶2    def lowestCommonAncestor(self, root, p, q):
▶3        if not root or root is p or root is q:
▶4            return root
▶5        left = self.lowestCommonAncestor(root.left, p, q)
▶6        right = self.lowestCommonAncestor(root.right, p, q)
▶7        if left and right: return root
▶8        return left or right

05

Edge cases

p is an ancestor of q

Recursion stops at p without exploring below — p returns as its own LCA, correct by the definition.

Targets on the same side

Only that child returns non-None; the answer bubbles from within it.

06

Complexity

Time

O(n)

Space

O(h)

Single DFS, no parent pointers needed.