236. Lowest Common Ancestor of a Binary Tree

Time: O(n)

Space: O(h)

Intuition

Post-order DFS: we need information from both subtrees before deciding. If a node equals p or q, return it immediately - even if the other target is a descendant, the current node is still the LCA. If both left and right recursive calls return non-null, we are at the node where p and q split - that's the LCA.

Algorithm

1Base cases: if root is null, return null. If root == p or root == q, return root.
2Recurse: left = LCA(root.left, p, q); right = LCA(root.right, p, q).
3If both left and right are non-null -> root is the LCA. Return root.
4Otherwise return whichever is non-null (the LCA is deeper in that subtree).

Example Walkthrough

Input: root=[3,5,1,6,2,0,8,null,null,7,4], p=5, q=4

1.DFS left of 3: reaches 5. 5 == p -> return node 5.
2.From 5, DFS right: reaches 2, then 4. 4 == q -> returns up through 2, then 5.
3.Back at node 3: left returned node 5 (found p). Dive right of 3: reaches 1,0,8 - none match p or q -> returns null.
4.Node 3: left=node5 (non-null), right=null -> return node5 as LCA.

Output: Node with value 5

Common Pitfalls

•The algorithm assumes both p and q exist in the tree. If either is missing, the result is undefined.
•Do NOT descend into a subtree after finding one target - the early return `if root == p || root == q` handles the ancestor case correctly.

236.cs

// Approach: Post-order DFS — recurse into both subtrees before deciding at each node.
// Base cases: return null for a null node; return the node itself if it equals p or q.
// After recursing left and right: if both return non-null, the current root is the LCA.
// If only one side is non-null, that value is the LCA candidate and propagates up.
// This single DFS pass handles all cases: p is ancestor of q, q is ancestor of p, and the general case.
// Time: O(n) Space: O(h) for the recursion stack where h is the tree height.

public class TreeNode
{
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int x) { val = x; }
}

public class Solution
{
    public TreeNode LowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q)
    {
        if (root == null || root == p || root == q)
            return root;

        TreeNode left = LowestCommonAncestor(root.left, p, q);
        TreeNode right = LowestCommonAncestor(root.right, p, q);

        if (left == null)
            return right;
        if (right == null)
            return left;
        else
            return root;
    }
}

Was this solution helpful?