Deepest Leaves Sum
Medium · Trees · Tree · Depth-First Search · Breadth-First Search · Binary Tree
Problem
Given the root of a binary tree, return the sum of the values on its deepest level: the level farthest from the root.
Every node on the deepest level is a leaf, but not every leaf is on the deepest level. Leaves higher up do not count.
The tree is given in level order, with None for a missing child. from_level([3,5,1]) builds it and to_level(root) turns it back into a list.
Examples
Input: root = [3,5,1,6,2,None,8,None,None,7,4] Output: 11
The deepest level holds 7 and 4. Leaves 6 and 8 are higher up and do not count.
Input: root = [9,4] Output: 4
Only 4 is on the deepest level.
Input: root = [1,2,3,4,5,6,7] Output: 22
4 + 5 + 6 + 7 = 22.
Constraints
- 1 <= number of nodes <= 10^4
- 1 <= Node.val <= 100
Approaches
- Baseline: height first, then a second walk — time O(n), space O(h)
Follow-up
The level walk holds one level at a time, O(w) memory for a tree of width w; a depth-first walk with a running "deepest so far" holds O(h). The use cases ask for the shallowest leaves instead, and for any level counted from the bottom.
Related problems
Start free on Cariara · Coding problems · System design studio
