Lowest Common Ancestor of a Binary Tree
Problem Statement
Given the root of a binary tree and two distinct nodes p and q that both exist in the tree, return their lowest common ancestor. The lowest common ancestor is the deepest node that has both p and q as descendants, where a node can be a descendant of itself.
Input
The root pointer of a general binary tree, plus references to the two target nodes p and q. This is not a BST problem, so values do not determine direction.
Output
The tree node that is the deepest shared ancestor of p and q.
Constraints
- •
2 <= number of nodes <= 10^5 - •
-10^9 <= Node.val <= 10^9 - •
All Node.val values are unique - •
p and q are different nodes and both exist in the tree
Examples
Example 1
root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
3Example 2
root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
5Learning Objectives
- Recognise when a binary-tree LCA problem needs full DFS instead of BST ordering.
- Use postorder recursion to bubble target discoveries back to their parent.
- Explain why returning **p** or **q** immediately is correct when one target is an ancestor of the other.
- Contrast the general-tree solution with the compare-and-branch BST version.
Intuition
Pattern Recognition
The technique is postorder bubble-up for LCA. The signal is a general binary tree where there is no ordering rule, so you cannot decide left or right from values. That is the key difference from tree-lca-bst, where BST ordering lets you walk downward by comparing p.val, q.val, and root.val.
In a general tree, each node asks its children a yes-or-no style question: did your subtree find either target? If the left side returns a target and the right side returns a target, the current node is the lowest place where both targets are seen. If only one side returns a node, bubble that node upward. If the current node is p or q, return it immediately because it may be the ancestor that absorbs the other target below.
Common mistakes
- ×Using BST comparison logic even though the input is only a binary tree.
- ×Continuing below **p** or **q** before returning it, which complicates the ancestor case unnecessarily.
- ×Returning **null** when only one child finds a target instead of bubbling the non-null side upward.
- ×Thinking the first target found in DFS is the answer; the answer is where the two returned paths meet.
Algorithm Explanation
Key idea
Run a postorder DFS. Each recursive call returns one of three meanings: null if the subtree found neither target, p or q if it found exactly one target, or the final LCA if both targets were already found inside that subtree. The parent only needs to combine the left and right returns.
Recursion walkthrough
Use [3,5,1,6,2,0,8,null,null,7,4] with p = 5 and q = 4. The call at node 5 hits p, so it returns 5 immediately to node 3. The fact that 4 is lower inside the same subtree does not change the answer because 5 is allowed to be an ancestor of itself.
For p = 5 and q = 1 on the same tree, the left recursion from 3 returns 5 and the right recursion returns 1. Node 3 receives two non-null answers from different sides, so 3 is the first common meeting point and returns itself. Every ancestor above would only bubble 3 upward.
Algorithm
- If root is null, return null.
- If root is exactly p or q, return root.
- Recursively search the left subtree and store the returned node.
- Recursively search the right subtree and store the returned node.
- If both sides returned non-null nodes, return root because the targets split across the two sides.
- Otherwise return the non-null side, or null if neither side found a target.
Solutions
Solution: Postorder DFS bubble-up
Use this for the standard general binary-tree LCA problem. It does not assume sorted values and naturally handles the case where one target is an ancestor of the other.
Search both subtrees before deciding what the current node represents. A non-null return means this subtree has found one target or has already found the answer. When both child calls return non-null, the current node is the LCA.
Step-by-step
- Return null for an empty subtree.
- Return root immediately when root is p or q.
- Ask the left child for a target or completed answer.
- Ask the right child for a target or completed answer.
- If both answers exist, return root.
- Otherwise bubble up whichever side is non-null.
O(n)
O(h)
Every node may be visited once, and the recursion stack height is **h**, which is **n** in a skewed tree.
Java implementation
Dry Run
Sample input
root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1. Track the returns into node 3.
| call | left return | right return | decision | return |
|---|---|---|---|---|
| node 5 | not needed | not needed | current node is **p** | 5 |
| node 1 | not needed | not needed | current node is **q** | 1 |
| node 3 | 5 | 1 | both sides are non-null | 3 |
The left and right subtrees of 3 each report one target, so 3 is the lowest node where the two paths meet.
Interview Tips
Say explicitly whether the tree is a BST. If it is not, avoid value comparisons and describe the postorder contract: each call returns null, one found target, or the completed LCA. Interviewers like hearing the ancestor case: when root == p or root == q, returning root lets the other target below confirm that this node is the answer.
Likely follow-ups
- How would the solution change for a Binary Search Tree such as **tree-lca-bst**?
- What if either **p** or **q** might be missing from the tree?
- How would you find the LCA of more than two target nodes?
- How would parent pointers change the strategy?
Similar Problems
Key Takeaways
- General binary-tree LCA is a postorder search, not a BST compare-and-branch walk.
- A call returns **null**, a target, or an already discovered LCA.
- Two non-null child returns make the current node the lowest meeting point.
- Returning **p** or **q** immediately correctly handles ancestor-of-target cases.