Average of Levels in Binary Tree

Leetcode#637

Photo by Kanhaiya Sharma on Unsplash

Leet Code Question:

Average of Levels in Binary Tree - LeetCode

The key to solving this problem is performing BFS or Level order traversal of the tree.

if we take above “Example 1”, the level order traversal is:

[[3],[9,20],[15,7]]

so their respective averages list is:

[3/1, 29/2, 22/2]

=> [3.0,14.5,11] (ans)

So for BFS traversal, we can take the help of a Queue, to push elements at each level. So that we can calculate avg over each level.

Java Code:

O/P:

Time Complexity:

The time complexity of the above solution is O(n) and requires O(n) extra space, where n is the size of the binary tree.

We can also solve this problem by using hashing. The idea is to traverse the tree in a preorder fashion and store every node and its level in a multimap using the level number as a key. Finally, print all nodes corresponding to every level starting from the first level. We can also traverse the tree in an inorder or postorder fashion.

Thanks for your read and 👏👏

#arraysinjava. #array #datastructures #codinginterviewquestions #codinginterview #faang #leetcode #animated #java #python #faang #motion