Maximum Level Sum of a Binary Tree

MediumTreeslevel order

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

Levels of a binary tree are numbered starting at 1 for the root, 2 for its children, and so on. The sum of a level is the total of all node values on it. Given the root of a non-empty binary tree, return the level number whose sum is largest. If several levels tie for the largest sum, return the **smallest** such level number. Values may be negative, so do not assume deeper levels are larger. A BFS over levels runs in O(n).

Examples

Input: root = [1,7,0,7,-8,null,null]
Output: 2
Level sums are 1, 7 and -1; level 2 is largest.
Input: root = [989,null,10250,98693,-89388,null,null,null,-32127]
Output: 2
Level 2 contains only 10250, which beats every other level sum.

Constraints

  • 1 <= number of nodes <= 10^4
  • -10^5 <= Node.val <= 10^5

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.

More level order problems