Average of Levels in Binary Tree — Day 90(Python)

Today’s question is an easy-tagged question in Leetcode. It is from Daily Coding Challenge — March edition. Let us look into the problem statement.

Given a non-empty binary tree, return the average value of the nodes on each level in the form of an array.

Example 1:

Note:

1. 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.

Complexity analysis.

Time Complexity

Since we are traversing through the entire tree once, the time complexity is O(N).

Space Complexity

Space complexity is O(N) since we are storing all the nodes in queues.

More from Annamariya Tharayil

Software Engineer. Find me @ www.linkedin.com/in/annamariya-jt

Elevator Pitch For Buttonless Elevators

Get the Medium app