DSA problem
Average of Levels in Binary Tree
Given the root of a binary tree, return the average value of the nodes on each level in the form of an array. Answers within 10^-5 of the true value are accepted.
This is a textbook level-order problem. Each level of the tree is processed as a self-contained batch: we sum the node values on the level, divide by the count, and append the result to the output array. The tree's structure is incidental — only the grouping of nodes by depth matters.
The key implementation subtlety is numeric overflow. Node values can be as large as 2^31 - 1 in magnitude, and a level may contain up to about 10^4 nodes. The sum can therefore exceed the 32-bit signed integer range, so in Java the running sum must be a long (or you can use double directly), and in C++ a long long. In Python and JavaScript the native number types handle this automatically.
We implement a standard BFS: enqueue the root, then for each outer iteration snapshot the queue size, dequeue exactly that many nodes, accumulate their values into a wide-enough sum, enqueue their children, and finally push sum / size (as a floating-point number) to the result. The algorithm visits each node once, giving O(n) time and O(w) space.
Examples
root = [3,9,20,null,null,15,7][3.0, 14.5, 11.0]root = [3,9,20,15,7][3.0, 14.5, 11.0]root = [1][1.0]Constraints
- The number of nodes in the tree is in the range [1, 10^4].
- -2^31 <= Node.val <= 2^31 - 1
- Answers within 10^-5 of the actual answer are accepted.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.