Show problems as
Classic problem #637EasyTreeDepth-First SearchBreadth-First SearchBinary Tree

Average of Levels in Binary Tree

Real-world version: Average Reading Per Tree Tier
Tracked in this browser only
Read Average of Levels in Binary Tree on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A monitoring rig is wired as a binary tree. Each station holds one integer reading and has at most two downstream stations, a left one and a right one.

The rig arrives as readings, a flat level-order encoding of that tree. Entry 0 is the root station's reading. After that, taking the present stations in level-order, each one claims the next two entries as its left child slot and then its right child slot; a slot holding null means that child is absent. Slots that would sit past the end of the list are absent too, so trailing null entries may be left off.

Group the stations by tier, where the root sits in tier 0 and a child sits one tier below its parent. Return the mean reading of each tier, ordered from tier 0 downwards. Each returned value is a decimal number and is accepted when it is within 1e-5 of the true mean.

Examples

Example 1

Input
readings = [4, 2, 9, 1, null, 6, 8]
Output
[4.0, 5.5, 5.0]

Tier 0 holds the single reading 4. Tier 0's two child slots give tier 1 the readings 2 and 9, whose mean is 5.5. Station 2 has a left child reading 1 and no right child, and station 9 has children reading 6 and 8, so tier 2 holds 1, 6 and 8 with mean 5.

Example 2

Input
readings = [6, 5, 4, -1, 0, 2]
Output
[6.0, 4.5, 0.3333333333333333]

Tier 1 holds 5 and 4. Station 5 claims entries 3 and 4, reading -1 and 0; station 4 claims entry 5, reading 2, and its right slot falls past the end of the list, so it is absent. Tier 2 therefore holds -1, 0 and 2, whose mean is one third.

Example 3

Input
readings = [7, 3, 12]
Output
[7.0, 7.5]

The root reads 7, so tier 0 has mean 7. Its two children read 3 and 12, so tier 1 has mean 7.5, and neither child claims any further entries.

Constraints

  • The rig holds between 1 and 10^4 stations.
  • 1 <= readings.length <= 2 * 10^4 + 1
  • -2^31 <= readings[i] <= 2^31 - 1
  • readings[0] is a reading, never null.

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def average_per_tier(readings: list) -> list[float]:
Java
public double[] averagePerTier(Integer[] readings)

More on the same topics