Richest Level of a Tree

Medium

You get the root root of a binary tree. The root sits on level 1, its children on level 2, their children on level 3, and so on. For every level, add up the values of its nodes, and return the number of the level with the largest sum. If several levels tie, return the topmost one, i.e. the smallest number. Node values can be negative.

Example 1

root=tree_node([2, -4, 9, 6, None, -1, 3]) → 3

Level sums are 2, then -4 + 9 = 5, then 6 + (-1) + 3 = 8. The largest is on level 3.

Example 2

root=tree_node([5, 3, 2, -6, 1]) → 1

Levels 1 and 2 both sum to 5, level 3 sums to -5. On a tie the higher level wins, so the answer is 1.

Example 3

root=tree_node([-3]) → 1

Constraints

1 ≤ number of nodes ≤ 10⁴
-10⁵ ≤ Node.val ≤ 10⁵

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Tree Depth-First Search Breadth-First Search Binary Tree

Similar problems

The Tree Seen From the Right Medium Tree Columns, Top Down Medium First Value on the Lowest Row Medium Largest Value on Each Tree Level Medium Insert a Tree Level Medium

Input

root=tree_node([2, -4, 9, 6, None, -1, 3])

Expected

Run checks the first 3 tests in your browser. Submit checks all 91 tests on the server, hidden ones included.