Smallest Subtree With All Deepest Nodes
01 · Problem
Given the root of a binary tree with distinct values, find the deepest nodes: the nodes whose distance from the root is the largest. Return the smallest subtree that contains all of them, that is, the subtree rooted at their lowest common ancestor.
If there is only one deepest node, the answer is that node itself (a subtree with just that node and its descendants, which are none). The returned subtree is serialised in level-order form starting from its root, with null marking missing children (trailing nulls omitted).
02 · Examples
root = [3,5,1,6,2,0,8,null,null,7,4]
[2,7,4]
The deepest nodes are 7 and 4 at depth 3. Their lowest common ancestor is 2, so the subtree rooted at 2 is returned.
root = [1]
[1]
The root is the only, and therefore deepest, node.
root = [0,1,3,null,2]
[2]
Node 2 is the single deepest node, so the answer is the subtree containing only 2.
03 · Constraints
- 01The number of nodes in the tree is in the range [1, 500].
- 020 <= Node.val <= 500
- 03All node values are unique.
04 · Optimal complexity
- Time
- O(n)
- Space
- O(h)
Practice it alone or rehearse it as an interview.
Practice Mode gives you an editor and test runs, nothing else. AI Interview Mode puts a voice interviewer on the other side, adds a clock, and ends with a scored summary of the round.