[Facebook Question] Average of levels in a Binary Tree

Problem: Given a binary tree, return the average value of the nodes on each level in the form of an array.

Example:

Input:
    1
   / \
  6  10
    /  \
   11   7
Output: [1, 8, 9]
Explanation: The average value of nodes on level 0 is 1,  on level 1 is (10 + 6) / 2 = 8, and on level 2 is (11 + 7) / 2 = 9. Hence return [1, 8, 9].

Approach: A simple level order traversal / BFS can solve this question. Just look at the implementation directly to understand the approach.

Implementation in C#:

    public IList<double> AverageOfLevels() 

    {

        List<double> result = new List<double>();

        if (this.Rroot == null)

        {

            return result;

        }

        Queue<TreeNode> queue = new Queue<TreeNode>();

        queue.Enqueue(this.Root);

        while (queue.Count > 0)

        {

            int size = queue.Count;

            double sum = 0;

            for (int i = 0; i < size; ++i)

            {

                BinaryTreeNode node = queue.Dequeue();

                sum += node.Value;

                if (node.LeftNode != null)

                {

                    queue.Enqueue(node.LeftNode);

                }

                if (node.RightNode != null)

                {

                    queue.Enqueue(node.RightNode);

                }

            }

            result.Add(sum / size);

        }

        return result;

    }

Complexity: O(n)