Average of Levels in Binary Tree - shilpathota/99-leetcode-solutions GitHub Wiki

Average of Levels in Binary Tree

Leet code Link - https://leetcode.com/problems/average-of-levels-in-binary-tree/

Complexity - Easy

Description

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, 104].
-231 <= Node.val <= 231 - 1

Solution

We can use BFS or DFS here to get the numbers of each level and then perform average

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public Map<Integer,List<Double>> levelOrder(TreeNode node){
        //2 approaches
        // recursion
        // without recursion
        //BFS
         Map<Integer,List<Double>> list = new HashMap<Integer,List<Double>>();
        Queue<Pair<TreeNode,Integer>> q = new ArrayDeque<>();
        q.add(new Pair<>(node,0));
        while(!q.isEmpty()){
            Pair<TreeNode,Integer> current= q.poll();
            TreeNode newNode = current.getKey();
            int level = current.getValue();
            if(list.get(level)==null){
                list.put(level,new ArrayList<>());
            }
            list.get(level).add((double)newNode.val);
            if(newNode.left!=null) q.add(new Pair<>(newNode.left,level+1));
            if(newNode.right!=null) q.add(new Pair<>(newNode.right,level+1));
        }
        return list;
    } 
    public List<Double> averageOfLevels(TreeNode root) {
        List<Double> output = new ArrayList<>();
        Map<Integer,List<Double>> listval = levelOrder(root);
        int levelsList = listval.size();
        for(int i=0;i<levelsList;i++){
            List<Double> list = listval.get(i);
            Double Sum = list.stream().mapToDouble(Double::doubleValue).sum();
             DecimalFormat df = new DecimalFormat("#.#####");
            Double formattedDoubleSum = Double.parseDouble(df.format((double)Sum/list.size()));
            output.add(formattedDoubleSum);
        }
        return output;
    }
}

Time Complexity - O(N)

Space Complexity - O(N)

⚠️ **GitHub.com Fallback** ⚠️