📖 7 min read
Last updated on

Lowest Common Ancestor of a Binary Tree — Coding Interview Walkthrough

By intervu.dev

You’re in a coding interview. The interviewer draws a binary tree on the whiteboard, circles two nodes, and asks you to find their lowest common ancestor. You recognize it’s a tree problem, reach for the BST shortcut of comparing values, and the interviewer stops you: “This isn’t a BST.” Now you need a different strategy entirely, and the recursive approach you’re about to attempt has a subtle edge case that trips up most candidates: a node can be its own ancestor.

This walkthrough covers how that conversation should go: why the single-pass postorder DFS works, how to handle every edge case cleanly, and what strong candidates say before writing a line of code.

The Problem

Given a binary tree and two nodes p and q, find their lowest common ancestor (LCA).

The lowest common ancestor is defined as the deepest node in the tree that has both p and q as descendants (a node can be a descendant of itself).

(LeetCode #236)

Example

Input

Tree:
        3
       / \
      5   1
     / \ / \
    6  2 0  8
      / \
     7   4

p = 5, q = 4

Output 5

Explanation: Node 5 is the LCA of nodes 5 and 4 because 5 is an ancestor of 4, and 5 is a descendant of itself by definition. Another example: if p = 5 and q = 1, the LCA would be 3 (the root).

Binary tree [3,5,1,6,2,0,8,null,null,7,4] with node 5 highlighted as LCA of p=5 and q=4. The path from node 5 down to node 4 through node 2 is highlighted in teal.

Already comfortable with the solution? Practice it in a mock interview →

What Interviewers Are Actually Testing

This problem isn’t just about trees. It’s a rich signal for several core engineering skills.

SkillWhat Interviewers Observe
Recursive thinkingCan you define the base case and trust the recursion?
Tree traversalDo you understand postorder traversal and why it applies here?
Edge case awarenessDo you handle when a node is its own ancestor?
CommunicationCan you explain why the algorithm works, not just what it does?
Problem decompositionDo you break the problem into smaller subproblems naturally?

Step 1: Clarifying Questions

1. Are all node values unique? LeetCode guarantees this, but confirming it lets you reason clearly about identity checks. If values could repeat, you’d need to compare node references, not values.

2. Are p and q guaranteed to exist in the tree? Yes. If either could be missing, you’d need to traverse the entire tree before returning an answer. This guarantee simplifies the algorithm.

3. Can a node be its own ancestor? Yes, and this is a key edge case. If p is an ancestor of q, then p itself is the LCA.

4. Is this a BST or a general binary tree? This matters. A BST allows a simpler, iterative solution using value comparisons. For a general binary tree, we need a different strategy.

Step 2: A First (Non-Optimal) Idea

The brute-force approach finds the path from the root to each node, then compares both paths.

def find_path(root, target, path):
    if root is None:
        return False
    path.append(root)
    if root == target:
        return True
    if find_path(root.left, target, path) or find_path(root.right, target, path):
        return True
    path.pop()
    return False

def lca_brute(root, p, q):
    path_p, path_q = [], []
    find_path(root, p, path_p)
    find_path(root, q, path_q)
    lca = None
    for a, b in zip(path_p, path_q):
        if a == b:
            lca = a
    return lca

This is correct but traverses the tree twice, stores entire paths (O(H) space each), and has higher constant factors. Interviewers will probe for something more elegant.

Step 3: The Key Insight

Solve this in a single pass using postorder DFS. If a node equals p or q, return it. Otherwise, recurse into both subtrees. If both sides return non-null, the current node is the LCA. If only one side returns non-null, propagate that result upward. This handles every case, including the self-ancestor edge case, because returning a node when we find it naturally propagates the answer up the call stack.

Why this works:

  • If the current node is p or q, we don’t need to go deeper. The other target must be somewhere in this subtree or above, making this node the LCA.
  • If p is in the left subtree and q is in the right subtree, the current node is the split point: the LCA.
  • If both are in the same subtree, the recursion naturally returns the correct answer up the chain.

Step 4: Optimal Strategy

  1. Base case: If the current node is None, return None.
  2. Match check: If the current node is p or q, return the current node immediately.
  3. Recurse left: Call the function on the left child.
  4. Recurse right: Call the function on the right child.
  5. Decision:
    • If both left and right returned non-null, the current node is the LCA.
    • If only one is non-null, return that one.
    • If both are null, return None.

Python Implementation

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution:
    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:
        # Base case: fallen off the tree
        if root is None:
            return None

        # If the current node matches either target, it's a candidate for LCA
        if root == p or root == q:
            return root

        # Recursively search both subtrees
        left = self.lowestCommonAncestor(root.left, p, q)
        right = self.lowestCommonAncestor(root.right, p, q)

        # If both subtrees returned a match, current node is the LCA
        if left and right:
            return root

        # Otherwise, propagate whichever subtree found a match
        return left if left else right

Why root == p and not root.val == p.val? We compare node references (object identity), not values. The problem passes actual TreeNode objects.

Time & Space Complexity

AspectComplexityExplanation
TimeO(N)Visit every node once in the worst case
Space (call stack)O(H)H = tree height. O(log N) balanced, O(N) skewed

Time: Even if we find p early, we may still need to search the other subtree for q.

Space: No additional data structures. Space is purely from the recursion stack.

Common Interview Mistakes

  1. Confusing BST LCA with general tree LCA. BST LCA uses value comparisons (go left if both values are smaller). That approach does not work for a general binary tree. Always confirm the tree type.

  2. Returning early on the first match without considering the subtree. Some candidates stop searching as soon as they find p. The algorithm handles this correctly because returning p naturally propagates the answer upward.

  3. Not handling the self-ancestor edge case. “A node can be a descendant of itself” is explicitly stated. The solution handles this because we return the node as soon as we find it.

  4. Coding before clarifying. Jumping into code without asking about BST vs. general tree is a common signal of poor interview habits.

  5. Not explaining the postorder nature of the traversal. Interviewers love hearing “this is essentially a postorder DFS because we make decisions based on what our children return.” Naming the pattern shows depth.

  6. Forgetting to return the result upward. A common bug is finding the LCA but not propagating it correctly. Make sure return root in the “both sides non-null” case actually returns up the call stack.

  7. Using extra space unnecessarily. Storing paths or using a hash map of ancestors works, but introducing O(N) extra space when O(H) is achievable costs points.

What a Strong Candidate Sounds Like

“Before I code, I want to confirm: this is a general binary tree, not a BST, right? And both p and q are guaranteed to be in the tree? Great. My approach is a single-pass postorder DFS. For each node, I’ll recurse into both children. If a node equals p or q, I return it immediately, which covers the case where a node is its own ancestor. Once both children have returned, if both are non-null, the current node is the split point and therefore the LCA. If only one is non-null, I propagate it upward. This gives O(N) time and O(H) space for the call stack.”

Example Interview Dialogue

Interviewer: Can you walk me through your approach before you code?

Candidate: I’ll do a postorder DFS: recurse into both children first, then decide what to return at the current node. If either child returns a non-null result, that means one of our targets was found in that subtree. If both children return non-null, the current node is the LCA. If only one does, I pass it up.

Interviewer: What happens if p is an ancestor of q?

Candidate: When we reach p, we return it immediately. As we unwind the recursion, p bubbles up. Since q is somewhere below p, the other subtree will return null. So we end up returning p, which is correct.

Interviewer: What’s the space complexity?

Candidate: The recursion stack can go as deep as the tree’s height. For a balanced tree that’s O(log N), but in the worst case with a completely skewed tree, it’s O(N). No additional data structures, so space is purely from the call stack.

LCA is the foundation of a family of tree problems that build on postorder reasoning:

Practice This in a Mock Interview

Reading a solution is very different from performing under interview pressure. When you’re live with an interviewer, you need to handle clarifying questions in real-time, verbalize your thought process, adapt when you get follow-ups, and debug under a time constraint.

The only way to get comfortable with that experience is to simulate it. Understanding the algorithm is step one. Executing it confidently in a live setting is what gets you the offer.

Start a mock interview for Lowest Common Ancestor on Intervu.

Further reading:

Practice Like It's the Real Interview

Get instant feedback on your approach, communication, and code — powered by AI.

Start a Mock Interview →