Lowest Common Ancestor of a Binary Tree
Medium · Graphs · Explanation and code example
Breadth First Search
How it works
Instead of recursion, we can use BFS to build a parent pointer map for each node. Once we have parent pointers, we trace the path from p to the root and store all ancestors. Then we trace from q upward until we hit a node that's already in p's ancestor set. That node is the LCA.
Steps
- Use BFS to traverse the tree, storing each node's parent in a hash map.
- Continue BFS until both
pandqare found in theparentmap. - Create an
ancestorsset and trace frompto the root, adding each node to the set. - Trace from
qupward until finding a node that exists in theancestorsset. - Return that node as the LCA.
Complexity
- Time complexity:
O(n) - Space complexity:
O(n)
Things to watch for
Returning Early Without Checking Both Subtrees
A common mistake in the recursive approach is returning as soon as you find p or q, without considering that the other target might be in a different subtree. The correct approach returns the current node if it matches a target, but the parent call must still check both subtree results to determine if the current node is the LCA.
Confusing Node Reference with Node Value
The problem asks for the LCA of specific nodes p and q, not nodes with values p.val and q.val. Since tree nodes can have duplicate values, you must compare node references (node == p) rather than values (node.val == p.val). Using value comparison fails when multiple nodes share the same value.
Mishandling the Case Where One Node is Ancestor of the Other
When p is an ancestor of q (or vice versa), the LCA is the ancestor node itself. A common bug is failing to recognize this case and continuing to search unnecessarily. In the optimal recursive solution, returning the node immediately when it matches p or q naturally handles this case, since the other target will be found in that node's subtree.
Python code example
from collections import deque
# Definition for a binary tree node.
# 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':
parent = {root: None}
queue = deque([root])
while p not in parent or q not in parent:
node = queue.popleft()
if node.left:
parent[node.left] = node
queue.append(node.left)
if node.right:
parent[node.right] = node
queue.append(node.right)
ancestors = set()
while p:
ancestors.add(p)
p = parent[p]
while q not in ancestors:
q = parent[q]
return q
C++ code example
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if (!root) return nullptr;
unordered_map<TreeNode*, TreeNode*> parent;
queue<TreeNode*> queue;
parent[root] = nullptr;
queue.push(root);
while (!parent.count(p) || !parent.count(q)) {
TreeNode* node = queue.front(); queue.pop();
if (node->left) {
parent[node->left] = node;
queue.push(node->left);
}
if (node->right) {
parent[node->right] = node;
queue.push(node->right);
}
}
unordered_set<TreeNode*> ancestors;
while (p) {
ancestors.insert(p);
p = parent[p];
}
while (!ancestors.count(q)) {
q = parent[q];
}
return q;
}
};
Source and license
Adapted from NeetCode’s source · MIT license. Node types are supplied by LeetCode where needed.