Find the lowest common ancestor of all deepest leaves in a binary tree.
Problem
Given the root of a binary tree, return the node that is the lowest common ancestor (LCA) of all the tree's deepest leaves.
A leaf is a node with no children. The deepest leaves are the leaves that have the maximum depth from the root. If there is only one deepest leaf, the answer is that leaf itself.
The LCA of a set of nodes is the deepest node in the tree that is an ancestor of every node in the set.
Your task
Write a function that identifies the subtree containing the deepest leaves and returns the node that is the common ancestor of all of them.
Input Format
- The input is the
rootof a binary tree. - The tree is provided in the usual node-based representation used by the platform.
Output Format
- Return a reference to the tree node that is the lowest common ancestor of all deepest leaves.
Constraints
- The tree is non-empty.
- The tree has at most one root.
- Node values are not necessarily unique.
- A valid answer always exists.
Example 1
Input
root = [3,5,1,6,2,0,8,null,null,7,4]
Output
[2,7,4]
Explanation
The deepest leaves are 7 and 4, and their lowest common ancestor is node 2.
Example 2
Input
root = [1]
Output
[1]
Explanation
The single node is both the only leaf and the LCA of the deepest leaves.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.