# Java BFS Solution

• Classic bfs problem. At each level, compute the average since you already know the size of the level.

``````public List<Double> averageOfLevels(TreeNode root) {
List<Double> result = new ArrayList<>();

if(root == null) return result;
while(!q.isEmpty()) {
int n = q.size();
double sum = 0.0;
for(int i = 0; i < n; i++) {
TreeNode node = q.poll();
sum += node.val;
if(node.left != null) q.offer(node.left);
if(node.right != null) q.offer(node.right);
}
}
return result;
}``````

• Not sure am I correct or not.
I think the root is just one node of the tree, but not the whole tree, so q.add(root) just add a TreeNode into the linkedlist.

• @zhiwlin Yes, it adds only the root node.

• @jaqenhgar oh my bad, you do recursion by adding the nodes to q, at first I thought the while loop will just run one times ......

• Most elegant java solution. Clean code - Cheers.

• Almost same code. LOL

``````public class Solution {
public List<Double> averageOfLevels(TreeNode root) {
List<Double> res = new ArrayList();
if(root == null) return res;
queue.offer(root);
while(!queue.isEmpty()){
int size = queue.size();
double sum = 0;
for(int i = 0;i < size;i++){
TreeNode cur = queue.poll();
if(cur.left != null) queue.offer(cur.left);
if(cur.right != null) queue.offer(cur.right);
sum += cur.val;
}
}
return res;
}
}
``````

• really clean solution. Thanks.

• same idea as me, I use Stack instead.

``````    public IList<double> AverageOfLevels(TreeNode root) {
IList<double> rs = new List<double>();
Stack<TreeNode> rsk = new Stack<TreeNode>();
rsk.Push(root);
return helper(rs, rsk);
}

public IList<double> helper(IList<double> rs, Stack<TreeNode> rsk)
{
if(rsk.Count == 0)return rs;
Stack<TreeNode> next = new Stack<TreeNode>();
double isum = 0;
double icount = 0;
while(rsk.Count > 0)
{
TreeNode cur = rsk.Pop();
isum += cur.val;
icount++;
if(cur.left != null)next.Push(cur.left);
if(cur.right != null)next.Push(cur.right);
}
return helper(rs, next);
}``````

• I don't like editorial solution attached to this problem. It creates too many LinkedList objects. My solution creates only one queue and uses null in a queue as a level termination value. But I like your approach better

``````public class Solution {
public List<Double> averageOfLevels(TreeNode root) {
List<Double> res = new ArrayList<>();
if (root == null) {
return res;
}
double sum = 0;
long count = 0;
while (!queue.isEmpty()) {
root = queue.poll();
if (root == null) {
if (!queue.isEmpty()) {
}
sum = 0;
count = 0;
} else {
sum += root.val;
count++;
if (root.left != null) {
}
if (root.right != null) {
}
}
}
return res;
}
}
``````

• @jaqenhgar I think the root contains all information of the tree, because it would recursive in the beginning of the root, am I right? I am not so sure acturally, please tell me if you are willing to.

• Cool. I used a similar algo but with two stacks.

``````public List<Double> averageOfLevels(TreeNode root) {

List<Double> averageList = new ArrayList<>();
stack1.push(root);
while (!stack1.isEmpty() || !stack2.isEmpty()) {
double average = 0;
long sum = 0, count = 0;
while (!stack1.isEmpty()) {

TreeNode t = stack1.pop();
sum += t.val;
count++;
if (t.left != null)
stack2.push(t.left);
if (t.right != null)
stack2.push(t.right);

}
if (count != 0) {
average = (double) sum / count;
}

average = 0;
sum = 0;
count = 0;

while (!stack2.isEmpty()) {

TreeNode t = stack2.pop();
sum += t.val;
count++;
if (t.left != null)
stack1.push(t.left);
if (t.right != null)
stack1.push(t.right);

}
if (count != 0) {
average = (double) sum / count;