Lowest Common Ancestor of a Binary Tree
Find the lowest node in a binary tree whose subtree contains both target nodes.
Problem Summary
Original task summary for this archive page. The official LeetCode prompt is linked in the header instead of being mirrored here.
Given the root of a binary tree and two node pointers \(p\) and \(q\), return their lowest common ancestor.
The tree is not a binary search tree, so you cannot rely on value ordering. The solution has to work from structure alone.
Recognition Pattern
How to notice the underlying interview pattern before writing code.
This is a postorder DFS on a tree problem.
In interviews, recognize it when:
the answer depends on information coming from both left and right subtrees
you are asked where two search paths first meet
the tree has no parent pointers and no BST ordering guarantee
Key Idea
The main invariant or observation that makes the clean solution work.
Let the recursive call answer a simple question: \emph{does this subtree contain \(p\), \(q\), or neither?}
The return rule is:
if the current node is null, return null
if the current node is \(p\) or \(q\), return the current node
recursively search left and right
if both sides return non-null, the current node is the lowest common ancestor
otherwise return the non-null side
This works because the first node that receives one target from each side is exactly where the two paths merge.
Step-by-step Reasoning
How to move from the obvious brute-force idea to the interview-ready solution.
One workable approach is to build the full root-to-node path for both targets, then compare the two paths until they diverge. That is correct, but it spends extra memory storing information you do not actually need to keep.
The cleaner observation is that each subtree only needs to report whether it found one of the targets. That makes the problem naturally recursive.
Postorder traversal is the right direction because the current node can only decide its role after both children have already reported what they found. If both children report success, the current node is the split point. If only one side reports success, the answer is still deeper on that side.
Complexity
Time and memory costs for the implementation shown below.
Time: \(O(n)\)
Space: \(O(h)\), where \(h\) is the tree height
C++ Solution
The exact repository source used for this LeetCode solution page.
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* };
*/
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if (root == nullptr || root == p || root == q) {
return root;
}
TreeNode* leftResult = lowestCommonAncestor(root->left, p, q);
TreeNode* rightResult = lowestCommonAncestor(root->right, p, q);
if (leftResult != nullptr && rightResult != nullptr) {
return root;
}
return leftResult != nullptr ? leftResult : rightResult;
}
};
Common Pitfalls
Real implementation mistakes that show up often in interviews and submissions.
Compare node pointers, not just node values. The problem is about the actual target nodes.
Do not assume BST ordering rules. This problem is for a general binary tree.
Remember that one target can be the ancestor of the other. Returning the current node immediately when it matches \(p\) or \(q\) handles that case correctly.
Variants / Follow-ups
Nearby problems and the next generalization to learn once this pattern is stable.
Nearby variants include Lowest Common Ancestor of a Binary Search Tree, Lowest Common Ancestor III with parent pointers, and multi-node ancestor questions.
The reusable pattern is a postorder DFS where each subtree returns just enough information for its parent to decide.
Source Files and Assets
Raw files are still available here when you want the original TeX, C++, or statement assets.
Show raw files
competitive_programming/leetcode/tree/lowest-common-ancestor-of-a-binary-tree/editorial.texC++ implementationcompetitive_programming/leetcode/tree/lowest-common-ancestor-of-a-binary-tree/solution.cppMetadatacompetitive_programming/leetcode/tree/lowest-common-ancestor-of-a-binary-tree/meta.json