Given a binary tree, write a method to return the level that has the maximum sum. In case the tree is empty, return **-1**

Example: 1 / \ 2 3 / \ / \ 4 5 6 7 / 8 Output ==> 2

**Note:** Assume that root is at level 0.

Need a **hand?** Try out these hints, one at a time.

Use a

`Queue`

to traverse the tree level by level.
1. Declare the `Queue`

to store the nodes.

2. Declare four record keeping variables - `current level`

, `max level`

, `current level sum`

and `maximum sum`

. Initialize them to `0`

.

3. Queue the `root`

.

4. Loop till the `Queue`

becomes empty.

5. Within the loop, dequeue a node.

6. If the current element is `null`

, compare the `current level sum`

with the `maximum sum`

and update the tracking variables accordingly.

7. Reset the `current level sum`

variable and increent the level. Insert `null`

into the `Queue`

if the `Queue`

is not empty.

8. If the `current element`

is `not null`

, add its data to `current level sum`

and insert `left`

and `right`

nodes into the queue.

9. At the end of the loop, return the `level`

with `maximum sum`

.

public int findMaxSumLevel(TreeNode root) { }

**C**

**Java**

**Python**