Find the smallest subtree that contains every node at the maximum depth of a binary tree.
Problem
Given the root of a binary tree, return the root node of the smallest subtree that contains all of the tree's deepest nodes.
A node is considered deepest if its depth from the root is maximal among all nodes in the tree. If there is only one deepest node, the answer is that node itself.
The returned subtree must include every deepest node, and among all such subtrees, it should be the one rooted as low as possible in the tree.
Intuition
The key is to compare the deepest depth in the left and right subtrees. The answer is:
- the left subtree result if the left side is deeper,
- the right subtree result if the right side is deeper,
- the current node if both sides reach the same maximum depth.
Input Format
- A binary tree root node.
- The tree is described using level-order style representation in examples.
Output Format
- Return the root node of the smallest subtree containing all deepest nodes.
Constraints
- The tree is a binary tree.
- Node values are distinct in the standard interview formulation.
- The tree may have zero, one, or many nodes.
Hints
- Compute the depth of each subtree while also propagating the candidate answer upward.
- Think of the problem as finding where the deepest nodes from both sides first meet.
Input Format
- Binary tree root.
- In examples, the tree is shown in level-order notation.
Output Format
- The root node of the smallest subtree containing all deepest nodes.
Constraints
- Binary tree size and shape are arbitrary.
- Return the deepest common ancestor that covers every node at maximum depth.
Example 1
Input
root = [3,5,1,6,2,0,8,null,null,7,4]
Output
[2,7,4]
Explanation
The deepest nodes are 7 and 4, both at the same maximum depth. The smallest subtree containing both is rooted at 2.
Example 2
Input
root = [1]
Output
[1]
Explanation
There is only one node, so it is also the deepest node and the answer.
Show 1 more example
Example 3
Input
root = [1,2,3,4]
Output
[4]
Explanation
Node 4 is the only deepest node, so the smallest subtree is the node itself.
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.