How to Solve: Lowest Common Ancestor (LCA) of a BST / Binary Tree

How to Solve: Lowest Common Ancestor (LCA) of a BST / Binary Tree

(Complete Guide for FAANG-Level Interviews)

? Introduction

"This problem appears in 1 out of every 3 onsite interviews—master it, and you’ll prove you can leverage tree properties, optimize traversals, and handle edge cases like a senior engineer."

? WHAT YOU NEED TO KNOW FIRST

Before tackling LCA, ensure you understand: 1. Binary Tree Traversals (DFS/BFS) – In-order, pre-order, post-order, and level-order traversals. 2. BST Properties – Left subtree < root < right subtree (for BST variants). 3. Recursion & Backtracking – Essential for tree problems (especially DFS).

? KEY TECHNIQUES & PATTERNS

? STEP-BY-STEP FRAMEWORK

(Repeatable mental checklist for every LCA problem)

1. Clarify the Problem

• Is it a BST or a general binary tree?
• BST: Use BST properties for optimization.
• General tree: Use DFS/BFS.
• Are p and q guaranteed to exist in the tree?
• If not, handle None cases.
• Can p be an ancestor of q (or vice versa)?
• Yes → LCA is the ancestor itself.

2. Choose the Right Approach

3. Implement the Base Case

• If root is None → Return None.
• If root is p or q → Return root.

4. Traverse Left & Right Subtrees

• Recursive DFS:
• left = dfs(root.left, p, q)
• right = dfs(root.right, p, q)
• BST Optimization:
• If p.val < root.val and q.val < root.val → Traverse left.
• If p.val > root.val and q.val > root.val → Traverse right.
• Else → root is LCA.

5. Determine the LCA

• If both left and right return non-None → root is LCA.
• If only one subtree returns non-None → Return that subtree’s result.
• If both are None → Return None.

6. Edge Cases & Validation

• One node is the ancestor of the other → LCA is the ancestor.
• One node not in tree → Return None (if problem allows).
• Tree is empty → Return None.

7. Optimize for Time/Space

• BST: O(h) time, O(1) space (iterative).
• General Tree: O(n) time, O(h) space (recursion stack).
• Follow-up: Preprocess parent pointers (O(n) time, O(n) space).

✅ WORKED EXAMPLES

Example 1 – Basic: LCA in a BST (LeetCode 235)

Problem: Find LCA of two nodes in a BST.

Thought Process

1. BST Property: If both p and q are < root, go left.
2. If both > root, go right.
3. Else, root is LCA.

Solution Code (Python)

def lowestCommonAncestor(root, p, q):

    while root:

        if p.val < root.val and q.val < root.val:

            root = root.left

        elif p.val > root.val and q.val > root.val:

            root = root.right

        else:

            return root

Complexity

• Time: O(h) (height of tree, worst case O(n) for skewed tree).
• Space: O(1) (iterative).

Why This Works

• BST property allows pruning one subtree at each step.

Example 2 – Medium: LCA in a General Binary Tree (LeetCode 236)

Problem: Find LCA of two nodes in a general binary tree.

Thought Process

1. Recursive DFS: Traverse left and right.
2. If both subtrees return non-None, root is LCA.
3. If only one subtree returns non-None, propagate that result.

Solution Code (Python)

def lowestCommonAncestor(root, p, q):

    if not root or root == p or root == q:

        return root

    left = lowestCommonAncestor(root.left, p, q)

    right = lowestCommonAncestor(root.right, p, q)

    if left and right:

        return root

    return left if left else right

Complexity

• Time: O(n) (visit every node once).
• Space: O(h) (recursion stack, worst case O(n)).

Why This Works

• Post-order traversal ensures we check subtrees before the root.

Example 3 – Hard/Follow-up: LCA with Parent Pointers (No Recursion)

Problem: Find LCA when nodes have parent pointers (no recursion allowed).

Thought Process

1. Store path from p to root in a set.
2. Traverse from q to root, checking if any node is in p’s path.
3. First match is LCA.

Solution Code (Python)

def lowestCommonAncestor(p, q):

    ancestors = set()

    while p:

        ancestors.add(p)

        p = p.parent

    while q:

        if q in ancestors:

            return q

        q = q.parent

    return None

Complexity

• Time: O(h) (height of tree).
• Space: O(h) (storing path for p).

Why This Works

• Parent pointers allow bottom-up traversal without recursion.

❌ Common Mistakes

? INTERVIEW TrapS

? 1-Minute Recap

"Alright, let’s lock this in. For LCA problems, here’s your 30-second cheat sheet:

1. BST? Use BST properties—compare values to prune subtrees.
2. General tree? Recursive DFS: check left/right, return root if both subtrees have matches.
3. No recursion? Use parent pointers or iterative DFS.
4. Edge cases: One node missing? One node is ancestor? Handle them.
5. Follow-ups: Binary lifting for multiple queries, parent pointers for O(1) space.

Now go crush that interview—you’ve got this!

? Final Notes

• Practice: LeetCode 235 (BST), 236 (General Tree), 1644 (LCA with missing nodes).
• Follow-ups: Binary lifting, LCA in a forest, LCA with path length.
• Time: BST (O(h)), General Tree (O(n)), Parent Pointers (O(h)).

Every line here is whiteboard-ready. Good luck! ?