King Of Interviews

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 actual answer will be accepted.

Example 1:

Input: root = [3,9,20,null,null,15,7]
Output: [3.00000,14.50000,11.00000]
Explanation: 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].

Example 2:

Input: root = [3,9,20,15,7]
Output: [3.00000,14.50000,11.00000]

Constraints:

The number of nodes in the tree is in the range [1, 10^4].
-2^31 <= Node.val <= 2^31 - 1

Try this Problem on your own or check similar problems:

Solution:

public List<Double> averageOfLevels(TreeNode root) {
    Queue<TreeNode> q = new LinkedList<>();
    List<Double> result = new ArrayList<Double>();
    q.add(root);

    while(!q.isEmpty()){
        int size = q.size(), numberOfElements = size;
        double sum = 0;
        while(numberOfElements-->0){
            TreeNode node = q.poll();
            sum += node.val;
            if(node.left != null){
                q.add(node.left);
            }
            if(node.right != null){
                q.add(node.right);
            }
        }
        result.add(sum / numberOfElements);
    }

    return result;
}

Time/Space Complexity:

Time Complexity: O(n)
Space Complexity: O(n)

Explanation:

Classic BFS (Breadth-first search) of the tree. Since we use a queue the space complexity is linear O(n). To go over tree level by level we start by adding the root to the queue. Then each iteration of the outer loop we poll all the elements (current level). For each polled element we check if it has left and right child, if it does we add them to the queue and they become the next level nodes. After each iteration of outer loop, we store the average in list and return the list as the final result.

Average of Levels in Binary Tree