Lowest Common Ancestor of a Binary Tree
Asked at Google, Meta, Amazon, Microsoft, Apple, Netflix, Uber, Atlassian
Problem
Given a binary tree, find the lowest common ancestor (LCA) of two given nodes p and q. The lowest common ancestor is the deepest node that has both p and q as descendants.
Asked At
| Company | Difficulty | |
|---|---|---|
| Medium | View all Google questions → | |
| Meta | Medium | View all Meta questions → |
| Amazon | Medium | View all Amazon questions → |
| Microsoft | Medium | View all Microsoft questions → |
| Apple | Medium | View all Apple questions → |
| Netflix | Medium | View all Netflix questions → |
| Uber | Medium | View all Uber questions → |
| Atlassian | Medium | View all Atlassian questions → |
How to Think About It
Recursive approach: if the current node is null, p, or q, return it. These are the base cases.
Recurse on left and right children. If both return non-null, the current node is the LCA (p and q are in different subtrees).
If only one side returns non-null, that side contains both nodes (or one of them). Pass that result up.
If neither returns non-null, neither subtree contains p or q. Return null.
Why it works: the recursion naturally finds the deepest node where p and q's paths diverge. That's the LCA.
Visual walkthrough for tree: 3
/ \n 5 1
/ / \n 6 2 0 8
/ /
7 4
LCA(5, 1): left returns 5, right returns 1 → current node 3 is LCA.
LCA(5, 4): left returns 5 (contains both), right returns null → LCA is 5.
LCA(7, 4): left subtree: 7 returns 7, 4 returns 4 → 5 is LCA (both in 5's subtree).
Edge cases: p is ancestor of q (p is LCA), q is ancestor of p (q is LCA), same node (that node is LCA).
Optimal Approach
Step 1: Base case — if root is null, or root equals p or q, return root.
Step 2: Recurse: left = lca(root.left, p, q), right = lca(root.right, p, q).
Step 3: If both left and right are non-null, current node is LCA → return root.
Step 4: Return the non-null one (or null if both are null).
Time: O(n) — visit every node in worst case. Space: O(h) — recursion stack.
What Trips People Up in Real Interviews
Confusing this with LCA of a BST. In a BST, you can use the BST property to narrow the search. In a general binary tree, you can't.
Not handling the case where one node is the ancestor of the other. If p is an ancestor of q, p is the LCA.
Forgetting the base case: if the current node is null, p, or q, return it.
Trying to find the LCA by storing paths. That's O(n) space and more complex than the recursive approach.
Not handling the case where p and q are the same node. If p == q, that node is the LCA of itself. The algorithm handles this through the base case, but some candidates add unnecessary logic.
Solution Code
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 or rightFrequently Asked Questions
What is the Lowest Common Ancestor of a Binary Tree problem?
Given a binary tree, find the lowest common ancestor (LCA) of two given nodes p and q. The lowest common ancestor is the deepest node that has both p and q as descendants.
How do you solve Lowest Common Ancestor of a Binary Tree?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Lowest Common Ancestor of a Binary Tree?
Lowest Common Ancestor of a Binary Tree is asked at Google, Meta, Amazon, Microsoft, Apple, Netflix, Uber, Atlassian. It is a medium difficulty problem.
What are common mistakes on Lowest Common Ancestor of a Binary Tree?
- Confusing this with LCA of a BST. In a BST, you can use the BST property to narrow the search. In a general binary tree, you can't.
- Not handling the case where one node is the ancestor of the other. If p is an ancestor of q, p is the LCA.
- Forgetting the base case: if the current node is `null`, p, or q, return it.
- Trying to find the LCA by storing paths. That's `O(n)` space and more complex than the recursive approach.
- Not handling the case where p and q are the same node. If p == q, that node is the LCA of itself. The algorithm handles this through the base case, but some candidates add unnecessary logic.