Leetcode 637. Average of Levels in Binary Tree

Problem Explanation

This problem is about traversing a Binary Tree level by level and calculating the average value on each level and returning them in an array form. For example, let's consider the input tree:

1
2plaintext
3    3
4   / \
5  9  20
6    /  \
7   15   7

The first level contains one node 3 and the average is 3/1 = 3. The second level contains 9 and 20 and the average is (9+20)/2 = 14.5. The third level contains 15 and 7 and the average is (15+7)/2 = 11. Thus, the output is [3, 14.5, 11].

Approach

The solution uses Breadth-First Search (BFS) algorithm to traverse all nodes of the tree. BFS is a perfect fit for this problem because it explores all nodes at one depth level before moving to nodes at the next level. The algorithm works by enqueueing the root node to a queue then entering a loop that runs while the queue is not empty. In each iteration, it calculates the sum of all the node values at the same depth level and then computes the average by dividing the sum with the number of nodes on that level. It then enqueues left and right children of nodes for the next level.

Python Solution

1
2python
3class Solution:
4    def averageOfLevels(self, root):
5        if not root: return []
6        queue, res = [root], []
7        while queue:
8            n, level_sum = len(queue), 0
9            for i in range(n):
10                node = queue.pop(0)
11                level_sum += node.val
12                if node.left: queue.append(node.left)
13                if node.right: queue.append(node.right)
14            res.append(level_sum / n)
15        return res

Java Solution

1
2java
3class Solution {
4    public List<Double> averageOfLevels(TreeNode root) {
5        List<Double> result = new ArrayList<>();
6        Queue<TreeNode> queue = new LinkedList<>();
7        queue.offer(root);
8        while (!queue.isEmpty()) {
9            int size = queue.size();
10            double sum = 0;
11            for (int i = 0; i < size; i++) {
12                TreeNode node = queue.poll();
13                sum += node.val;
14                if (node.left != null) queue.offer(node.left);
15                if (node.right != null) queue.offer(node.right);
16            }
17            result.add(sum / size);
18        }
19        return result;
20    }
21}

JavaScript Solution

1
2javascript
3var averageOfLevels = function(root) {
4    let queue = [root];
5    let result = [];
6    while(queue.length > 0) {
7        let level = queue.length;
8        let sum = 0;
9        for(let i = 0; i < level; i++) {
10            let node = queue.shift();
11            sum += node.val;
12            if(node.left) queue.push(node.left);
13            if(node.right) queue.push(node.right);
14        }
15        result.push(sum/level);
16    }
17    return result;
18};

C++ Solution

1
2cpp
3class Solution {
4public:
5    vector<double> averageOfLevels(TreeNode* root) {
6        vector<double> result;
7        queue<TreeNode*> que;
8        que.push(root);
9        while (!que.empty()) {
10            long long sum = 0, count = 0;
11            queue<TreeNode*> temp;
12            while (!que.empty()) {
13                TreeNode* n = que.front();
14                que.pop();
15                sum += n -> val;
16                count++;
17                if (n -> left) temp.push(n -> left);
18                if (n -> right) temp.push(n -> right);
19            }
20            que = temp;
21            result.push_back(sum * 1.0 / count);
22        }
23        return result;
24    }
25};

C# Solution

1
2csharp
3public class Solution {
4    public IList<double> AverageOfLevels(TreeNode root) {
5        IList<double> result = new List<double>();
6        Queue<TreeNode> queue = new Queue<TreeNode>();
7        queue.Enqueue(root);
8        while(queue.Count > 0) {
9            long sum = 0, count = 0;
10            Queue<TreeNode> temp = new Queue<TreeNode>();
11            while(queue.Count > 0) {
12                TreeNode n = queue.Dequeue();
13                sum += n.val;
14                count++;
15                if (n.left != null) temp.Enqueue(n.left);
16                if (n.right != null) temp.Enqueue(n.right);
17            }
18            queue = temp;
19            result.Add(sum * 1.0 / count);
20        }
21        return result;
22    }
23}

This algorithm gives the solution in O(N) time and O(N) space complexity. It's important to understand that Breadth-first Search requires using a queue that can build up to store the entire bottom row of the tree, which can be up to N/2 nodes for a full binary tree.## PHP Solution

PHP is another popular web-based server-side language that can provide a solution to the same problem. The solution in PHP is similar to other programming languages, but it's unique because of PHP's built-in array functions.

1
2php
3class Solution {
4    function averageOfLevels($root) {
5        $queue = [$root];
6        while(!empty($queue)) {
7            $count = $level_sum = 0;
8            $temp_queue = [];
9            foreach($queue as $node) {
10                $level_sum += $node->val;
11                $count++;
12                if($node->left != null) $temp_queue[] = $node->left;
13                if($node->right != null) $temp_queue[] = $node->right;
14            }
15            $result[] = $level_sum/$count;
16            $queue = $temp_queue;
17        }
18        return $result;
19    }
20}

This PHP code uses arrays as queues for storage. It utilizes a temporary queue, temp_queue, to collect all nodes of the next level, while the current queue, queue, is used for the current level. The queue elements are extracted using a foreach loop, which is PHP’s version of the universal for loop in other languages.

Time Complexity and Space Complexity

The time complexity is O(N) because we are visiting each node exactly once. There are N nodes in the tree, so the total operations are linear in terms of the number of nodes.

The space complexity is also O(N) because, in a worst-case scenario, we may end up storing all nodes at a single level in the queue. In a complete binary tree, the number of nodes at the last level are approximately N/2, thus space complexity is O(N), where N is the total number of nodes in the tree.