Problem rundowns

LC 236 - Lowest Common Ancestor of Binary Tree

Pattern: Postorder DFS

Key Insight

• If current node is p or q, return it.
• Search left and right.
• If both return non-null ⇒ current node is LCA.
• Else return the non-null side.

Template

function dfs(node) {
    if (!node || node === p || node === q) {
        return node;
    }
 
    const left = dfs(node.left);
    const right = dfs(node.right);
 
    if (left && right) {
        return node; // LCA
    }
 
    return left || right;
}

Why it works

• p and q bubble up from subtrees.
• First node receiving one from left and one from right is the LCA.

Complexity

• Time: O(n)
• Space: O(h) recursion stack

Recognition

• Binary Tree (not BST)
• Need common ancestor of two nodes
• “First node where paths to p and q meet” ⇒ Postorder DFS.