Skip to main content

74. Lowest Common Ancestor of a Binary Tree

mediumAsked at Salesforce

Find the lowest common ancestor (LCA) of two nodes in a binary tree. Salesforce uses this in their role-hierarchy queries — 'find the common manager between two reports.'

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Source citations

Public interview reports confirming this problem appears in Salesforce loops.

  • Glassdoor (2026-Q1)— Salesforce role-hierarchy LCA in production.
  • Blind (2025-12)— Recurring on Salesforce backend onsites.

Problem

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree. The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).

Constraints

  • The number of nodes in the tree is in the range [2, 10^5].
  • -10^9 <= Node.val <= 10^9
  • All Node.val are unique.
  • p != q
  • p and q will exist in the tree.

Examples

Example 1

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

Example 2

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

Explanation: 5 is an ancestor of 4 and itself.

Approaches

1. Find paths, then walk in lockstep

Find paths from root to p and root to q. LCA is the last shared node.

Time
O(n)
Space
O(n)
function lowestCommonAncestor(root, p, q) {
  const pathTo = (target) => {
    const path = [];
    function go(n) {
      if (!n) return false;
      path.push(n);
      if (n === target) return true;
      if (go(n.left) || go(n.right)) return true;
      path.pop();
      return false;
    }
    go(root);
    return path;
  };
  const pp = pathTo(p), qp = pathTo(q);
  let i = 0;
  while (i < pp.length && i < qp.length && pp[i] === qp[i]) i++;
  return pp[i - 1];
}

Tradeoff: Two traversals + path storage. O(n) total but uses O(n) space and is less elegant.

2. Recursive single-pass

If node is p or q, return it. Recurse left/right. If both return non-null, current is LCA. Else return the non-null one.

Time
O(n)
Space
O(h)
function lowestCommonAncestor(root, p, q) {
  if (!root || root === p || root === q) return root;
  const left = lowestCommonAncestor(root.left, p, q);
  const right = lowestCommonAncestor(root.right, p, q);
  if (left && right) return root;
  return left || right;
}

Tradeoff: Elegant single-pass. The recursion exploits the invariant: if both sides return non-null, p and q are in different subtrees → current is LCA. Salesforce's preferred answer.

Salesforce-specific tips

Salesforce uses LCA in their role-hierarchy queries — 'who is the common manager between two reports?' They grade specifically on whether you handle the case where p is an ancestor of q (or vice versa). The base case `root === p || root === q` covers this. Bonus signal: extend to LCA of N nodes (Apex API for finding common manager of a list).

Common mistakes

  • Not returning the node itself when matched — the algorithm relies on p/q being treated as 'found' immediately.
  • Treating values instead of references — fails on duplicate values.
  • Forgetting that an ancestor of itself counts — the case where p is ancestor of q.

Follow-up questions

An interviewer at Salesforce may pivot to one of these next:

  • LCA of a BST (LC 235) — exploits BST structure for O(h).
  • LCA with parent pointers (LC 1650).
  • LCA in N-ary tree.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

Why return the node on match?

Because p/q are valid LCAs of themselves (the problem allows a node to be a descendant of itself). Returning early avoids deeper recursion.

Why does 'both sides non-null' mean current is LCA?

Because each side returning non-null means one of {p, q} is in that subtree. If they're in different subtrees, the current node is the lowest ancestor of both.

Practice these live with InterviewChamp.AI

Drill Lowest Common Ancestor of a Binary Tree and other Salesforce interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →