Lowest Common Ancestor of a Binary Tree

Intuition

Think about what each recursive call reports back: it returns a non-null node if either p or q (or their LCA) was found in that subtree. If the current node is null it found nothing, and if it equals p or q we can immediately report the current node upward. After searching both children, there are only three cases to reason about. When both the left and right calls come back non-null, p was found on one side and q on the other, which means the current node is exactly the split point and therefore the lowest common ancestor. When only one side returns non-null, both targets live in that side, so we bubble that result up unchanged.

Algorithm walkthrough

1. 1Base case: if the node is null, or it is p, or it is q, return the node itself so the caller learns a target was located here.
2. 2Recurse on the left child and store the result; recurse on the right child and store its result.
3. 3If both the left and right results are non-null, p and q were found in different subtrees, so return the current node as the LCA.
4. 4If exactly one side is non-null, return that side, propagating the found target (or already-found LCA) upward.
5. 5If both sides are null, return null so ancestors know nothing was found in this branch.
6. 6The very first call that satisfies the both-sides-non-null condition is the answer that surfaces at the top.

Implementation

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        if root is None or root is p or root is q:
            return root
        left = self.lowestCommonAncestor(root.left, p, q)
        right = self.lowestCommonAncestor(root.right, p, q)
        if left and right:
            return root
        return left if left else right