A binary tree is given as a single space-separated level-order array. Values appear top-to-bottom, left-to-right; the literal token null marks a missing child (a null never has children). An empty tree is encoded as the single token null.
Levels are numbered from the root: the root is level 0, its children are level 1, and so on. For each level, compute the sum of the values of the nodes on that level. Find the level with the largest such sum. If several levels tie for the largest sum, choose the one with the smallest level index.
Print that level index. If the tree is empty, print -1.
A single line of level-order tokens separated by single spaces. Each token is an integer or the literal null. The line may be exactly null for an empty tree.
A single integer: the smallest 0-indexed level whose sum is maximal, or -1 if the tree is empty.
Middle level wins
Input
1 7 0 7 -8 null null
Expected
1
Explanation
Level 0 sum = 1. Level 1 sum = 7 + 0 = 7. Level 2 has the children of node 7, namely 7 and -8, summing to -1. The largest level sum is 7 at level 1, so the answer is 1.
Tie broken by smaller index
Input
5 3 2 null null null 3
Expected
0
Explanation
Level 0 sum = 5. Level 1 sum = 3 + 2 = 5. Level 2 sum = 3. The maximum sum 5 occurs at both level 0 and level 1, so we choose the smaller index, 0.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →