Code Destine

Problem Statement

You have given a binary tree, return the average of all the nodes values on each level in the form of a list.

Example 

Average value of nodes on level 0 is 3, on level 1 is 14.5, on level 2 is 7.5 and on level 3 is 4.6. So result is [3, 14.5, 7.5, 4.6].   

Algorithm 

The level order traversal algorithm can be used to solve this problem. Level order traversal can be implemented by using standard tree algorithms like depth first search and breadth first search.

Breadth First Search

package com.leetcode.subscribe;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class AverageOfLevels {

	public static void main(String[] args) {
		
		AverageOfLevels pot = new AverageOfLevels();
		
		TreeNode node = new TreeNode(3);
		node.left = new TreeNode(9);
		node.right = new TreeNode(20);		
		
		node.left.left = new TreeNode(2);
		node.left.right = new TreeNode(6);	
		
		TreeNode node1 = new TreeNode(15);
		TreeNode node2 = new TreeNode(7);
		
		node.right.left = node1;
		node.right.right = node2;	
		
		node1.left = new TreeNode(5);
		node1.right = new TreeNode(8);
		
		node2.right = new TreeNode(1);
		
		List<Double> result = pot.averageOfLevels(node);
		for(Double i : result) {
			System.out.print(i+", ");
		}
	}
	
	public List<Double> averageOfLevels(TreeNode root) {
        
        List<Double> result = new ArrayList<>();
        if(root == null){
            return result;
        }
        
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        int size = 0, i = 0;
        double sum = 0;
        while(queue.size() > 0){            
            sum = 0;
            size = queue.size();
            for(i = 0; i < size; i++){                
                root = queue.poll();
                sum = sum + (double)root.val;
                if(root.left != null) queue.add(root.left);
                if(root.right != null) queue.add(root.right);
            }
            result.add(sum/size);            
        }
        return result;
    }
	
	public static class TreeNode {		
		int val;
		TreeNode left;
		TreeNode right;
		
		TreeNode(int x) {
			val = x;
		}
	}	
}

Depth First Search

import java.util.ArrayList;
import java.util.List;

public class AverageOfLevels {

	public static void main(String[] args) {
		
		AverageOfLevels pot = new AverageOfLevels();
		
		TreeNode node = new TreeNode(3);
		node.left = new TreeNode(9);
		node.right = new TreeNode(20);		
		
		node.left.left = new TreeNode(2);
		node.left.right = new TreeNode(6);	
		
		TreeNode node1 = new TreeNode(15);
		TreeNode node2 = new TreeNode(7);
		
		node.right.left = node1;
		node.right.right = node2;	
		
		node1.left = new TreeNode(5);
		node1.right = new TreeNode(8);
		
		node2.right = new TreeNode(1);
		
		List<Double> result = pot.averageOfLevels(node);
		for(Double i : result) {
			System.out.print(i+", ");
		}
	}
	
	public List<Double> averageOfLevels(TreeNode root) {
        
        List<Double> result = new ArrayList<>();
        if(root == null){
            return result;
        }
        
        List<Double> sum = new ArrayList<>();
        List<Double> count = new ArrayList<>();
        
        dfs(root, 0, sum, count);
        for(int i=0; i<sum.size(); i++){
            result.add(sum.get(i)/count.get(i));
        }
        return result;
    }
    
    public void dfs(TreeNode node, int level, List<Double> sum, List<Double> count){
        
        if(node == null) return;
        
        if(sum.size() == level){
            sum.add(0.0);
            count.add(0.0);
        }
                
        sum.set(level, sum.get(level) + node.val);
        count.set(level, count.get(level) + 1);
        
        dfs(node.left, level+1, sum, count);
        dfs(node.right, level+1, sum, count);
    }
	
	public static class TreeNode {		
		int val;
		TreeNode left;
		TreeNode right;
		
		TreeNode(int x) {
			val = x;
		}
	}	
}

Result

3.0, 14.5, 7.5, 4.666666666666667,

Similar Post

1. Level Order Traversal of Binary Tree
2. Minimum Distance Between BST Nodes
3. PreOrder Traversal of Tree

That’s all for Average of Levels in binary tree in Java, If you liked it, please share your thoughts in a comments section and share it with others too.