236. Lowest Common Ancestor of a Binary Tree
mediumFind the deepest node that has both p and q as descendants in a generic binary tree (not a BST). The recursive 'return whatever you find from either side' pattern is one of the most elegant in the canon.
By Alex Chen, Founder, InterviewChamp.AI · Last verified
Problem
Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree. According to the definition of LCA on Wikipedia: 'The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).'
Constraints
The number of nodes in the tree is in the range [2, 10^5].-10^9 <= Node.val <= 10^9All Node.val are unique.p != qp and q will exist in the tree.
Examples
Example 1
root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 13Example 2
root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 45Explanation: A node is allowed to be a descendant of itself.
Solve it now
Free. No sign-up. Python and JavaScript run instantly in your browser.
Hints
Progressive — try the first before opening the next.
Hint 1
Recurse. Base case: if node is null OR node == p OR node == q, return node.
Hint 2
Recurse into left and right. If both sides return non-null, the current node is the LCA.
Hint 3
If only one side returns non-null, propagate it up. That value is either the LCA found below, or the first of p/q seen on the way up.
Solution approach
Reveal approach
Post-order recursion that returns the LCA or whichever of p,q is found in the subtree. lca(node, p, q): if node is null, return null. If node == p or node == q, return node. Recurse left = lca(node.left, p, q) and right = lca(node.right, p, q). If both left and right are non-null, p and q were found in opposite subtrees so the current node is the LCA — return node. Otherwise return left if non-null else right. The genius is the dual meaning of the return value: 'either the LCA already established below, or the first p/q encountered.' At the moment both sides report back non-null, that ambiguity resolves into the answer. O(n) time, O(h) recursion space.
Complexity
- Time
- O(n)
- Space
- O(h)
Related patterns
- tree-dfs
- recursion
- post-order
Related problems
Asked at
Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).
- Amazon
- Meta
- Microsoft
- Apple
Practice these live with InterviewChamp.AI
Drill Lowest Common Ancestor of a Binary Tree and Trees problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.
Practice these live with InterviewChamp.AI →