Coding Interview: Find the Lowest Common Ancestor of a Binary Tree

Problem and Scope

Given an arbitrary binary tree and two distinct nodes p and q in it, return their lowest common ancestor. A node is its own ancestor. The LCA is the deepest node whose subtree contains both targets, so if p is an ancestor of q, the answer is p itself.

Four details define the base contract: the tree is not a binary search tree; inputs identify node objects rather than values; separate nodes may have the same value; and both p and q are guaranteed to be in the tree. Comparing values silently violates that contract. Reusing the base recursion after removing the existence guarantee also produces a subtle false positive.

a
      /   \
     b     c
    / \   / \
   d   e f   g
        \
         h

Here, LCA(d, h) = b, LCA(b, h) = b, and LCA(e, f) = a. This question targets software engineers expected to understand tree traversal, recursive semantics, and complexity. The base case asks for one query. Unbounded depth, absent targets, parent pointers, or many queries against one static tree are follow-up constraints that change the best solution.

What the Interviewer Is Evaluating

The first useful observation turns “lowest” into structure: the answer is the final common node on the root-to-p and root-to-q paths. Storing both paths is correct, but unnecessary. A sharper derivation asks every subtree to report one of three states: no target found, one target found, or the point where both targets have already met.

A strong answer defines the recursive return value precisely. For a subtree rooted at node, the function returns:

• null when the subtree contains neither p nor q;
• p or q when one discovered target must be propagated upward;
• another node when that node is already the LCA inside this subtree.

When both recursive results are non-null, the targets meet through different sides of the current node, so the current node is the answer. When only one side is non-null, its result propagates. The base case returns immediately when the current node is a target because existence is guaranteed: if the other target is below it, this node is the LCA; otherwise this node must report one target to an ancestor.

The contract trap matters. If q is absent, the base algorithm can return p; it does not also prove that both targets exist. Once the guarantee is removed, the recursive result needs a match count. For a tree with n nodes and height h, one query visits every node in the worst case, so time is O(n) and the recursive stack is O(h). In a skewed tree, h = n, and the call stack can become the failure rather than the algorithmic work.

Questions to Clarify First

• Are the inputs node references or values? References allow duplicate values, so compare with

node === p. Value lookup is valid only when uniqueness is part of the contract.

• Are both targets guaranteed to exist and be distinct? The base recursion relies on existence.

If either can be absent, return a match count too. If p === q is allowed, define whether finding that object once is sufficient.

• Is this an arbitrary binary tree or a binary search tree? An arbitrary tree needs structural

search. A BST can follow key order down one path, but duplicate keys and reference identity can invalidate that shortcut.

• What are the maximum node count and height? A balanced tree has O(log n) recursion depth.

A 100,000-node chain calls for an explicit stack and parent map to avoid runtime stack overflow.

• How many queries target the same static tree? A single query favors direct DFS. Many queries

can justify precomputing depth and 2^k ancestors for O(log n) queries.

• Do nodes already have parent pointers? Then the root need not be traversed. Align depths and

walk upward together, or record one ancestor chain and find its first intersection.

30-Second Answer Framework

“I would first confirm this is an arbitrary binary tree and that p and q are node references guaranteed to exist, so duplicate values do not affect identity. My recursive function returns the target or LCA discovered in a subtree. A null node returns null, and a node equal to p or q returns itself. After searching both children, two non-null results mean the targets meet at the current node; otherwise I propagate the one non-null result. Each node is visited at most once, giving O(n) worst-case time and O(h) stack space. I would test split branches, an ancestor target, duplicate values, and a skewed tree. If targets may be absent, I add a match count; if height is unbounded, I use an explicit stack to build parent links.”

Step-by-Step Solution

Step 1: Establish a Correct Path Baseline

The most direct approach finds the root-to-p and root-to-q paths, compares them from the root, and returns their final shared node. It explains the definition cleanly and naturally validates that both targets exist. Two DFS passes still take O(n) time, while the paths and recursion use O(h) space. An implementation that retains every explored node can grow to O(n) space.

The redundancy is that both searches traverse a large shared prefix. The only information needed is what a subtree reports to its parent, so the two paths can be compressed into one postorder traversal.

Step 2: Define the Return Value and Traverse Once

interface TreeNode {
  value: number
  left: TreeNode | null
  right: TreeNode | null
}

function lowestCommonAncestor(
  root: TreeNode | null,
  p: TreeNode,
  q: TreeNode,
): TreeNode | null {
  if (root === null || root === p || root === q) {
    return root
  }

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

  if (left !== null && right !== null) {
    return root
  }

  return left ?? right
}

The code compares object identity and never reads value, so equal values on separate nodes are safe. Postorder is essential: the current node needs both child reports before deciding whether it is the first meeting point.

Step 3: Prove It with an Invariant

Consider any subtree rooted at node, and assume both recursive calls satisfy the return-value definition.

1. If node is null, the subtree contains no target, so null is correct.
2. If node is p or q, return node. Since both targets exist, this target is either the LCA

because it contains the other target, or it must report one target to an ancestor.

1. If both child results are non-null, each side reports a target. No deeper node belongs to both

sides, so node is the deepest common ancestor.

1. If exactly one side is non-null, the current node creates no new meeting point. That side's

target or completed LCA is the only valid result to propagate. If both are null, return null.

By structural induction, the result returned at the root is the LCA of the full tree. The proof also covers the easy-to-miss ancestor case: when p is an ancestor of q, reaching p returns it without requiring q to be returned from below a second time.

Step 4: State the Real Time and Space Costs

In the worst case the function visits all n nodes and performs constant work at each, so time is O(n). Encountering a target early can skip part of the tree, but a best case is not the worst-case bound.

Auxiliary space is O(h) for recursion. In a balanced tree, h = O(log n); in a completely skewed tree, h = n. The returned node reference does not count as auxiliary storage. Calling the solution O(1) space ignores the call stack.

Step 5: Change the Contract When Targets May Be Missing

Without the existence guarantee, the base function can lie: if only p occurs in the tree, it propagates p all the way to the root. A safe version distinguishes a candidate node from the number of targets actually found.

interface SearchResult {
  candidate: TreeNode | null
  matches: number
}

function lowestCommonAncestorValidated(
  root: TreeNode | null,
  p: TreeNode,
  q: TreeNode,
): TreeNode | null {
  function visit(node: TreeNode | null): SearchResult {
    if (node === null) {
      return { candidate: null, matches: 0 }
    }

    const left = visit(node.left)
    if (left.matches === 2) {
      return left
    }

    const right = visit(node.right)
    if (right.matches === 2) {
      return right
    }

    const self = node === p || node === q ? 1 : 0
    const matches = left.matches + right.matches + self

    return {
      candidate: matches === 2 ? node : left.candidate ?? right.candidate ?? (self ? node : null),
      matches,
    }
  }

  const result = visit(root)
  return result.matches === 2 ? result.candidate : null
}

This version still assumes p !== q. If the same reference may be supplied twice, define the contract first: finding that node once should return it rather than continuing to require matches === 2. Constraint changes should precede code changes.

Step 6: Use an Explicit Stack and Parent Map for Deep Trees

When height can approach 100,000, the asymptotic recursion space is unchanged, but the runtime's call stack may overflow first. Traverse with an explicit stack and record parent.get(child) = node until both p and q are in the map. Put every ancestor of p into a set, then walk upward from q; the first set member is the LCA.

This alternative is still O(n) time and uses O(n) explicit space. It may use more heap memory than recursion, but moves the resource from a small call stack to controlled data structures. For one query on a tree with a reasonable height bound, the recursive version is shorter and easier to prove, so the parent map should not be the automatic default.

Step 7: Validate Semantics with Adversarial Cases

At minimum, cover this matrix:

| Case | Expected result | Bug exposed | |---|---|---| | p and q are on opposite root branches | Root | Searching only one path | | p is an ancestor of q | p | Forgetting self-ancestry | | Both nodes are deep in one subtree | Subtree node | Returning an ancestor that is too high | | Separate nodes have equal value | Correct object by identity | Treating value as identity | | One-node tree with p === q under an extended contract | That node | Undefined same-target behavior | | One target is absent | Validated version returns null | Base-version false positive | | A 100,000-node chain | Iterative version completes | Recursive stack overflow |

Beyond fixed examples, generate random small trees and compare the one-pass result with the path baseline by object identity. Because the baseline and optimized method use different approaches, this differential check catches more defects than a few hand-picked assertions alone.

High-Quality Sample Answer

“I would first lock down the contract: this is an arbitrary binary tree, p and q are distinct node references guaranteed to exist, and values may repeat. Therefore my code compares references, not values.

I use one postorder DFS. For a subtree, the function returns null, one discovered target, or an LCA already found. A null node returns null, and a current node equal to either target returns itself. After recursing into both children, two non-null results mean the targets first meet at the current node, so I return it. With only one non-null side, I propagate that result.

Correctness follows from that return invariant. When targets are in different child subtrees, no deeper node can contain both. When one target is the other's ancestor, returning the ancestor target immediately matches the definition. The worst case visits each node once for O(n) time, with O(h) recursive stack space; a skewed tree makes the stack depth O(n).

I would test opposite branches, an ancestor target, one deep subtree, and duplicate values. If targets are not guaranteed to exist, this function could return the one present target, so I would also return a match count and accept a candidate only after finding both. If the tree can be very deep, I would use an explicit stack and parent map to avoid call-stack overflow.”

Common Mistakes

• Treating the tree as a BST and choosing sides by value → arbitrary binary trees have no key

ordering, and duplicate values do not identify nodes → **search structure and compare node references.**

• Returning the current node when either child is non-null → a single target on one side gets

promoted all the way to the root → **return the current node only when both sides are non-null; otherwise propagate the non-null result.**

• Assuming p must be strictly below the answer → a node is its own ancestor, so p can be

the answer → make current-node identity a base case.

• Reusing the base algorithm when targets can be absent → finding one target still produces a

non-null result → return a match count and succeed only after finding both.

• Claiming O(1) auxiliary space → recursive frames grow with tree height and reach O(n) on

a chain → report O(h) and use an explicit stack when depth is unbounded.

• Precomputing binary lifting for one query → the code and O(n log n) storage are not

amortized → use one DFS for one query and preprocess only for many queries.

• Testing only two leaves on opposite sides → ancestor, duplicate-value, missing-target, and

depth bugs remain hidden → organize tests around contract boundaries.

Follow-Up Questions

What if p or q might not be in the tree?

Return both a candidate node and a match count from recursion. With distinct targets, the count is 0, 1, or 2. Return the candidate LCA only when the root result has count 2; otherwise return null. Running the base algorithm and merely checking for a non-null result is insufficient because the one present target is itself non-null.

What if the tree has 100,000 nodes and may be completely skewed?

Use an explicit stack to build a parent map. After both targets are found, store p's ancestors in a set and follow q's parent chain to the first intersection. It takes O(n) time and O(n) heap space but does not consume 100,000 language call frames. If heap space is also constrained, clarify whether parent pointers or a controlled traversal interface are available rather than assuming recursion is safe.

What if the same static tree must answer one million LCA queries?

An O(n) DFS per query no longer fits. Precompute each node's depth and its 2^k ancestors in O(n log n) time and space. For each query, lift the deeper node to the same depth, then lift both from the largest k downward, giving O(log n) per query. At still larger query volumes, an Euler tour plus RMQ may be worth evaluating; update frequency, memory, and latency requirements decide which preprocessing scheme is appropriate.

What if every node already has a parent pointer?

There is no need to traverse from the root. Compute both depths, raise the deeper node until depths match, then move both upward until they are equal. This takes O(h) time and O(1) extra space. Alternatively, store all of p's ancestors and walk upward from q; that is simpler but uses an O(h) set.

How does the solution change for a binary search tree?

With unique keys and a contract that locates targets by key, go left when both target keys are smaller, right when both are larger, and otherwise return the current split point or target. This takes O(h) time and O(1) iterative space. If values may repeat or inputs still identify targets by reference, define duplicate-key placement and lookup semantics first; two values alone cannot safely replace the arbitrary-tree algorithm.