Lowest Common Ancestor of a Binary Tree — Problem & Solution
Lowest Common Ancestor of a Binary Tree solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Lowest Common Ancestor of a Binary Tree is a medium coding problem on depth-first search and trees, asked in Amazon, Google, Microsoft and Meta interviews.
- Difficulty: Medium
- Topics: Depth-First Search, Trees
- Asked at: Amazon, Google, Microsoft, Meta
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given the root of a binary tree (not necessarily a search tree) whose node values are all distinct, and the values p and q of two different nodes in it.
The lowest common ancestor of two nodes is the deepest node that has both of them in its subtree — where a node counts as being in its own subtree, so a node can be the ancestor of itself. Return the value of the lowest common ancestor of the nodes holding p and q.
Example 1
Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
Output: 3
Explanation: 5 is in the root's left subtree and 1 in its right, so the deepest node holding both is the root 3.
Example 2
Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
Output: 5
Explanation: 4 lies below 5, and a node counts as its own descendant, so the answer is 5.
Example 3
Input: root = [1,2], p = 1, q = 2
Output: 1
Explanation: The root is an ancestor of 2 and of itself.
Constraints
2 <= number of nodes <= 10^5-10^9 <= Node.val <= 10^9all node values are distinctp != qp and q both exist in the tree
Hints for Lowest Common Ancestor of a Binary Tree
Hint 1
Without an ordering you have to search both subtrees, so think recursively: what should a subtree report back to its parent?
Hint 2
Let a call return the node holding
porqif it finds one (stopping there), and null if its subtree holds neither.Hint 3
If both the left and the right call come back non-null, the current node is where the two paths meet; otherwise pass up whichever side is non-null.
How to solve Lowest Common Ancestor of a Binary Tree
One post-order search answers "which of p and q are below here?" for every subtree; the first node that finds one target on each side — or is a target with the other below it — is the lowest common ancestor.
Approach
- Define
find(node): if the node is null, or holdsporq, return the node. - Otherwise call
findon the left and right children. - If both calls return a node, return the current node:
pandqare on different sides. - Otherwise return the non-null result (or null if both are null).
- The answer is the value of
find(root).
Why it works
find returns null exactly when its subtree holds neither target, and otherwise a node inside it. A call stops at the first target it meets; if the other target is below it, that target is never reached, and that is correct because the stopping node is then the ancestor. If the targets are in different child subtrees, both children report back and the current node is the deepest node containing both. Because the targets exist and are distinct, these cases cover everything, and the result bubbles up unchanged to the root.
Complexity
- Time —
O(n) - Space —
O(h) for the recursion
Pitfalls
- Stopping at a target is not a shortcut that loses the answer: if the other target is below it, this node is the ancestor.
- This relies on both values being present; with a missing value the function would wrongly return the one it found.
Reference solution
Python
from typing import Optional
def lowestCommonAncestor(root: Optional[TreeNode], p: int, q: int) -> int:
def find(node):
if node is None or node.val == p or node.val == q:
return node
left = find(node.left)
right = find(node.right)
if left and right:
return node
return left if left else right
return find(root).valJava
public static int lowestCommonAncestor(TreeNode root, int p, int q) {
return lcaFind(root, p, q).val;
}
static TreeNode lcaFind(TreeNode node, int p, int q) {
if (node == null || node.val == p || node.val == q) return node;
TreeNode left = lcaFind(node.left, p, q), right = lcaFind(node.right, p, q);
if (left != null && right != null) return node;
return left != null ? left : right;
}C++
TreeNode* lcaFind(TreeNode* node, int p, int q);
int lowestCommonAncestor(TreeNode* root, int p, int q) {
return lcaFind(root, p, q)->val;
}
TreeNode* lcaFind(TreeNode* node, int p, int q) {
if (!node || node->val == p || node->val == q) return node;
TreeNode* left = lcaFind(node->left, p, q);
TreeNode* right = lcaFind(node->right, p, q);
if (left && right) return node;
return left ? left : right;
}JavaScript
var lowestCommonAncestor = function(root, p, q) {
return lcaFind(root, p, q).val;
};
var lcaFind = function(node, p, q) {
if (node === null || node.val === p || node.val === q) return node;
var left = lcaFind(node.left, p, q), right = lcaFind(node.right, p, q);
if (left !== null && right !== null) return node;
return left !== null ? left : right;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 201 depth-first search problems · the whole catalogue
Learn the technique: Depth-First Search (DFS) · Binary Trees and Tree Traversals