Tree Level Averages

Binary TreeBreadth-First SearchTree

Given a binary tree, calculate the average value of the nodes on each level. The average should be in the form of a floating point value, rounded to two decimal places.

Example 1

Input

[
  {
    "val": 3,
    "left": {
      "val": 9,
      "left": null,
      "right": null
    },
    "right": {
      "val": 20,
      "left": {
        "val": 15,
        "left": null,
        "right": null
      },
      "right": {
        "val": 7,
        "left": null,
        "right": null
      }
    }
  }
]

Output

[3.00, 14.50, 11.00]

Explanation. The tree levels are 3, (9, 20), and (15, 7), with averages of 3.00, (9+20)/2 = 14.50, and (15+7)/2 = 11.00.

Example 2

Input

[
  {
    "val": 1,
    "left": null,
    "right": null
  }
]

Output

[1.00]

Explanation. The tree has only one node with value 1.

Follow-up: Can you solve the problem if the binary tree is modified to be a n-ary tree?

Constraints:

The binary tree will have at least one node.

Views: 2