Given a non-empty binary tree, return the average value of the nodes on each level in the form of an array.
Output: [3, 14.5, 11]
The average value of nodes on level 0 is 3, on level 1 is 14.5, and on level 2 is 11. Hence return [3, 14.5, 11].
- The range of node’s value is in the range of 32-bit signed integer.
We need to find the average value of nodes in each level. Since we need value for each level, it means we will have to use Level order traversal.
We can have a primary queue that holds the root node initially. All the immediate children of this node are saved in the secondary queue. Once the primary queue is empty, we will find the average of the values in the secondary queue and store them in our output array. We will replace the values in the primary queue with the values in the secondary queue and empty the secondary queue.
Let us look into the code snippet.
def averageOfLevels(self, root: TreeNode) -> List[float]:
queue = [root]
next_nodes = 
output = [root.val]
out = queue.pop(0)
if queue ==  and next_nodes:
s = 0
for i in next_nodes:
s += i.val
queue, next_nodes = next_nodes, queue
Since we are traversing through the entire tree once, the time complexity is O(N).
Space complexity is O(N) since we are storing all the nodes in queues.