532. Smallest Subtree with all the Deepest Nodes
You are given the root of a binary tree whose node values are all distinct. A node's depth is the number of edges from the root down to it; the tree's deepest nodes are the ones whose depth is maximal.
Among all subtrees that contain every deepest node, exactly one is smallest — return the value at its root. (A subtree here means a node together with all of its descendants.)
Equivalently: return the value of the lowest common ancestor of all the deepest nodes. When a single node is deepest, it is its own answer; when the deepest nodes are spread across both sides of some node, that node is the answer.
The tree arrives in level order, with null marking a missing child.
Example 1:
Input: root = [1, 2, 3, null, 4, 5, 6, null, null, 7, 8]
Output: 5
Explanation: The deepest nodes are 7 and 8, at depth 3. Both hang under node 5, and neither of node 5's own children contains them both — so the subtree rooted at 5 is the smallest one covering every deepest node.
Example 2:
Input: root = [1, 2, 3]
Output: 1
Explanation: Nodes 2 and 3 are both deepest (depth 1) and sit on opposite sides of the root, so only the whole tree contains them both.
Constraints:
- 1 ≤ number of nodes ≤ 500
- 0 ≤ Node.val ≤ 500, and all node values are distinct
Hints:
First find the maximum depth. If deepest nodes appear in both children's subtrees of some node, that node must be in every covering subtree — it is the answer. If they all sit on one side, the answer lies deeper on that side.
Two-pass version: record, for every node, the depth of the deepest leaf in its subtree. Then walk down from the root — equal deepest-depths on both sides means stop here; otherwise step into the deeper side.
One-pass version: make DFS return a pair (height of subtree, LCA of its deepest nodes). Equal child heights → the current node is the LCA; otherwise pass the taller child's pair upward.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: root = [1, 2, 3, null, 4, 5, 6, null, null, 7, 8]
Expected output: 5