637. Average of Levels in Binary Tree

EasyTreeDepth-First SearchBreadth-First SearchBinary Tree

Problem Description

The task is to calculate the average value of all the nodes on each level of a binary tree. A binary tree is a data structure where each node has at most two children, referred to as the left and the right child. In this context, a level refers to a set of nodes that are the same number of steps from the root. For example, the root itself is at level 0, its children are at level 1, the children's children are at level 2, and so on.

The input will be the root node of a binary tree, and the output should be a list of floating-point numbers, where each number represents the average value of the nodes at a corresponding level.

The problem states that the answer will be considered correct if it's within 10^-5 of the actual average. This means our solution does not need to be exact down to the last decimal place, allowing for a small margin of error, potentially due to floating-point precision issues.

Flowchart Walkthrough

Let's use the algorithm flowchart to analyze LeetCode problem 637. Average of Levels in Binary Tree. You can also follow visual steps using the Flowchart. Here is a detailed step-by-step analysis:

Is it a graph?

Yes: A binary tree is a specific type of graph.

Is it a tree?

Yes: Specifically, it is a binary tree.

Proceeding from the tree step in our flowchart:

Use DFS: Since the problem is directly related to a tree (binary tree), one effective way to traverse all nodes level by level, and compute the average at each level, is through Depth-First Search (DFS).

Using DFS in this context allows for easily tracking both the sum and count of values at each depth of the tree by utilizing recursion. This approach will enable the calculation of the average of nodes at each level efficiently.

Therefore, the flowchart suggests using DFS for efficiently solving the problem related to processing all levels of a binary tree.

Intuition

To find the average value of nodes at each level, we can use a technique called breadth-first search (BFS). This approach involves traversing the tree level by level from top to bottom and left to right and computing the average of the nodes' values at each level before moving on to the next one.

Here's how we can arrive at the solution:

We start by initializing a queue data structure and put the root node in it.
The queue will help us process all nodes level by level. For each level:
- We compute the total number of nodes at that level (this is the same as the number of elements currently in the queue).
- We then iterate over these elements, summing up their values and adding their children (if any) to the back of the queue to be processed in the next round.
- After processing all nodes in the current level, we calculate the average value by dividing the sum of the nodes' values by the total number of nodes.
- We append this average to our answer list.
Once the queue is empty, all levels have been processed, and our answer list contains the average of each level.
We return the answer list.

Using a queue in this manner ensures that we process all nodes at a given level before moving on to the next, enabling us to calculate the average per level efficiently.

A note on the implementation: In Python, we use deque from the collections module, as it provides an efficient way to pop elements from the left of the queue and to append elements to the right of the queue with O(1) time complexity for each operation, which is essential for maintaining the overall efficiency of the BFS algorithm.

Learn more about Tree, Depth-First Search, Breadth-First Search and Binary Tree patterns.

Solution Approach

The implementation follows the BFS pattern, using a queue to track nodes at each level. Here are the steps taken, matched with the code provided:

Queue Initialization: The queue is initialized with q = deque([root]), which will contain all nodes from the current level that we need to process.
Level Traversal: We use a while-loop while q: to continue processing nodes level by level until there are no more nodes left to process.
Level Processing: Within the while-loop, we perform these actions:
- s, n = 0, len(q): We start by storing the current level size n (which represents the number of nodes at the current level) and initialize a sum variable s to collect the sum of the nodes' values.
- A for-loop is used to iterate over each node in the current level: for _ in range(n):. For each node, we use q.popleft() to pop the leftmost node from the queue (representing the next node in the current level).
Node Processing and Child Enqueueing: Within the for-loop:
- We increment the sum with the current node's value: s += root.val.
- We check for children of the current node and enqueue them:
  - If a left child exists: if root.left:, we append it to the queue q.append(root.left).
  - Similarly, for a right child: if root.right:, we append it to the queue q.append(root.right).

Each iteration of the for-loop processes one node from the current level until all nodes at that level have been handled.

Average Calculation and Storage: After all nodes of the current level are processed, we calculate the average by dividing the sum s by the number of nodes n: ans.append(s / n). The result is then appended to the answer list ans.
Continuation and Completion: Once the for-loop finishes, the while-loop iterates again if there are any nodes left in the queue (these would be nodes from the next level that were enqueued during the for-loop). This process repeats until all levels are processed.
Returning the Result: After all levels have been iterated over and the while-loop exits, the answer list ans, now containing the averages of each level, is returned.

The solution uses a simple but effective linear-time algorithm that processes each node exactly once, giving an overall time complexity of O(n), where n is the number of nodes in the tree. The space complexity is O(m), where m is the maximum number of nodes at any level in the input tree (in the worst case, m could be up to n/2 for a full level in a perfectly balanced tree).

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's illustrate the solution approach with a concrete example. Consider the following binary tree:

We want to calculate the average value of all the nodes on each level of this tree.

Queue Initialization: Initialize the queue with the root node (which is 3).

q = deque([3])
Level Traversal: The while-loop begins since the queue is not empty.

while q:
Level Processing: For the first level (level 0 with the root node), we store the current queue size, which is 1, and the sum variable is initialized to 0.

s, n = 0, len(q) --> s, n = 0, 1

We then enter a for-loop to process this level's nodes.
Node Processing and Child Enqueueing: Pop the leftmost node (which is 3) and add its value to the sum.

s += 3

Since node 3 has two children (9 and 20), we enqueue those children.
```
q.append(9)
q.append(20)
```
Average Calculation and Storage: At the end of the level, we calculate the average by dividing the sum by the number of nodes, which in this case is just 3 / 1.

ans.append(3.0) --> ans = [3.0]
Continuation and Completion: The queue now contains two nodes for the next level (9 and 20). The while-loop continues for the next iteration.

For the second level (level 1), we again calculate the total nodes and sum.

s, n = 0, len(q) --> s, n = 0, 2

Pop each node, add its value, and enqueue any children (15 and 7 are enqueued).
```
s += 9
s += 20
q.append(15)
q.append(7)
```
Calculate and store the average for this level (29 / 2).

ans.append(14.5) --> ans = [3.0, 14.5]

The queue now contains the nodes for the next level (15 and 7), so the while-loop iterates again.

For the third level (level 2), we execute a similar process.

s, n = 0, len(q) --> s, n = 0, 2

No more children are enqueued at this level because neither 15 nor 7 have children.

Calculate and store the average (22 / 2).

ans.append(11.0) --> ans = [3.0, 14.5, 11.0]
Returning the Result: Now the queue is empty, and the while-loop exits. We return the list ans, which contains [3.0, 14.5, 11.0]. This list represents the average value of the nodes at each level of the given binary tree.

Solution Implementation

1from collections import deque
2
3class TreeNode:
4    # Definition for a binary tree node.
5    def __init__(self, val=0, left=None, right=None):
6        self.val = val
7        self.left = left
8        self.right = right
9
10class Solution:
11    def averageOfLevels(self, root: TreeNode) -> List[float]:
12        # Initialize a queue for breadth-first traversal with the root node
13        queue = deque([root])
14        # List to store the averages of each level
15        averages = []
16      
17        # Loop while there are nodes in the queue
18        while queue:
19            # Initialize the sum and get the number of nodes at the current level
20            level_sum, num_nodes = 0, len(queue)
21            # Iterate over all nodes at the current level
22            for _ in range(num_nodes):
23                # Pop the first node from the queue
24                node = queue.popleft()
25                # Add its value to the level sum
26                level_sum += node.val
27                # If there is a left child, add it to the queue
28                if node.left:
29                    queue.append(node.left)
30                # If there is a right child, add it to the queue
31                if node.right:
32                    queue.append(node.right)
33            # Calculate the average for the level and add it to the result list
34            averages.append(level_sum / num_nodes)
35          
36        return averages
37

1/**
2 * Definition for a binary tree node.
3 */
4class TreeNode {
5    int val;
6    TreeNode left;
7    TreeNode right;
8  
9    TreeNode() {}
10  
11    TreeNode(int val) { 
12        this.val = val; 
13    }
14  
15    TreeNode(int val, TreeNode left, TreeNode right) {
16        this.val = val;
17        this.left = left;
18        this.right = right;
19    }
20}
21
22class Solution {
23  
24    /**
25     * Computes the average of each level of a binary tree.
26     * @param root Root of the binary tree.
27     * @return List of averages of each level.
28     */
29    public List<Double> averageOfLevels(TreeNode root) {
30        List<Double> averages = new ArrayList<>(); // Stores the averages of each level
31        Deque<TreeNode> queue = new ArrayDeque<>(); // Queue for traversing the tree level by level
32        queue.offer(root); // Start with the root
33      
34        while (!queue.isEmpty()) {
35            int levelSize = queue.size(); // Number of nodes in the current level
36            long sum = 0; // Sum of values of nodes in the current level
37            // Iterate over all nodes in the current level
38            for (int i = 0; i < levelSize; ++i) {
39                TreeNode currentNode = queue.pollFirst(); // Get and remove the node from the queue
40                sum += currentNode.val; // Add the node's value to the sum
41                // Enqueue child nodes for the next level
42                if (currentNode.left != null) {
43                    queue.offer(currentNode.left);
44                }
45                if (currentNode.right != null) {
46                    queue.offer(currentNode.right);
47                }
48            }
49            averages.add((double)sum / levelSize); // Compute and add the average for this level to the result
50        }
51        return averages; // Return the list of averages
52    }
53}
54

1#include <vector>
2#include <queue>
3
4// Definition for a binary tree node.
5struct TreeNode {
6    int val;
7    TreeNode *left;
8    TreeNode *right;
9    TreeNode() : val(0), left(nullptr), right(nullptr) {}
10    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
11    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
12};
13
14class Solution {
15public:
16    vector<double> averageOfLevels(TreeNode* root) {
17        queue<TreeNode*> nodesQueue; // Queue to hold the nodes at the current level.
18        nodesQueue.push(root); // Start with the root node.
19        vector<double> averages; // Vector to store the average values of each level.
20
21        while (!nodesQueue.empty()) {
22            int levelSize = nodesQueue.size(); // Number of nodes at the current level.
23            long long levelSum = 0; // Sum of the values of nodes at the current level. Use long long to avoid integer overflow.
24
25            // Iterate over all nodes at the current level.
26            for (int i = 0; i < levelSize; ++i) {
27                TreeNode* currentNode = nodesQueue.front(); // Retrieve the front node in the queue.
28                nodesQueue.pop(); // Remove the node from the queue.
29                levelSum += currentNode->val; // Add the node value to the level sum.
30
31                // If the left child exists, add it to the queue for the next level.
32                if (currentNode->left) {
33                    nodesQueue.push(currentNode->left);
34                }
35                // If the right child exists, add it to the queue for the next level.
36                if (currentNode->right) {
37                    nodesQueue.push(currentNode->right);
38                }
39            }
40
41            // Calculate the average for the current level and add it to the result vector.
42            // Casting levelSum to double to get floating point division.
43            averages.push_back(static_cast<double>(levelSum) / levelSize);
44        }
45
46        return averages; // Return the vector containing averages of each level.
47    }
48};
49

1// Definition for a binary tree node.
2class TreeNode {
3    val: number;
4    left: TreeNode | null;
5    right: TreeNode | null;
6
7    constructor(val: number = 0, left: TreeNode | null = null, right: TreeNode | null = null) {
8        this.val = val;
9        this.left = left;
10        this.right = right;
11    }
12}
13
14/**
15 * Computes the average of the node values at each level of a binary tree.
16 * @param {TreeNode | null} root - The root of the binary tree.
17 * @return {number[]} - An array of averages, one for each level of the tree.
18 */
19function averageOfLevels(root: TreeNode | null): number[] {
20    let queue: Array<TreeNode | null> = [root]; // Initialize the queue with the root node.
21    let averages: number[] = []; // Initialize the array to hold averages of each level.
22
23    while (queue.length > 0) {
24        const levelSize: number = queue.length; // The number of nodes at current level.
25        let sum: number = 0; // Initialize sum of values at current level.
26
27        // Loop through nodes of the current level.
28        for (let i = 0; i < levelSize; i++) {
29            const currentNode = queue.shift(); // Remove the next node from queue.
30            if (currentNode) {
31                sum += currentNode.val; // Add the value of the current node to the level sum.
32
33                // If the current node has a left child, add it to the queue.
34                if (currentNode.left) {
35                    queue.push(currentNode.left);
36                }
37
38                // If the current node has a right child, add it to the queue.
39                if (currentNode.right) {
40                    queue.push(currentNode.right);
41                }
42            }
43        }
44
45        averages.push(sum / levelSize); // Compute and add the average to the result array.
46    }
47
48    return averages; // Return the array of averages.
49}
50
51// Example usage:
52// let tree = new TreeNode(3, new TreeNode(9), new TreeNode(20, new TreeNode(15), new TreeNode(7)));
53// let result = averageOfLevels(tree);
54// console.log(result); // Output: [3, 14.5, 11]
55

Time and Space Complexity

Time Complexity

The time complexity of the given code is O(N), where N is the number of nodes in the binary tree. This is because the algorithm uses a queue to traverse each node exactly once. During the traversal, each node's value is accessed and added to a sum, and its children are potentially added to the queue.

Space Complexity

The space complexity of the code can be considered as O(W), where W is the maximum width of the tree or the maximum number of nodes at any level of the tree. This occurs because the queue stores a level of the tree at most, which, in the worst case, can be all the leaf nodes of a full binary tree at the last level.

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

What are the two properties the problem needs to have for dynamic programming to be applicable? (Select 2)

Optimal substructure

Overlapping subproblems

Non-overlapping subproblems

Constant time subproblems