Lightest Tree Level

Medium

You are given the root of a binary tree whose nodes hold positive integers. Levels are numbered from the top: the root is on level 1, its children are on level 2, and so on. The weight of a level is the sum of the values of all nodes on it. Return the number of the level with the smallest weight. If several levels tie, return the one closest to the root (the smallest number).

Example 1

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

Level sums are 20, then 9 + 4 = 13, then 1 + 3 + 2 = 6. The lightest is level 3.

Example 2

root=tree_node([6, 2, 4]) → 1

Both levels weigh 6: the root alone and 2 + 4. On a tie the higher level wins, so the answer is 1.

Example 3

root=tree_node([15, 30, None, 8]) → 3

The sums are 15, 30 and 8, so level 3 is the lightest.

Constraints

The tree has between 1 and 10⁵ nodes
1 ≤ node value ≤ 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([20, 9, 4, 1, None, 3, 2])

Expected

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