637. Average of Levels in Binary Tree

EasyTreeDepth-First SearchBreadth-First SearchBinary Tree
Leetcode Link

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.

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:

  1. We start by initializing a queue data structure and put the root node in it.
  2. 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.
  3. Once the queue is empty, all levels have been processed, and our answer list contains the average of each level.
  4. 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.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece๏ผš

Which of these properties could exist for a graph but not a tree?

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:

  1. Queue Initialization: The queue is initialized with q = deque([root]), which will contain all nodes from the current level that we need to process.

  2. 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.

  3. 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).

  4. 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.

  1. 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.

  2. 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.

  3. 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).

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

How many ways can you arrange the three letters A, B and C?

Example Walkthrough

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

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

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

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

    q = deque([3])

  2. Level Traversal: The while-loop begins since the queue is not empty.

    while q:

  3. 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.

  4. 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.

    1q.append(9)
2q.append(20)

  5. 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]

  6. 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).

    1s += 9
2s += 20
3q.append(15)
4q.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]

  7. 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
Not Sure What to Study? Take the 2-min Quiz๏ผš

Breadth first search can be used to find the shortest path between two nodes in a directed graph.

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.

Fast Track Your Learning with Our Quick Skills Quiz:

How does quick sort divide the problem into subproblems?

Recommended Readings

Everything About Trees

Everything About Trees A tree is a type of graph data structure composed of nodes and edges Its main properties are It is acyclic doesn't contain any cycles There exists a path from the root to any node Has N 1 edges where N is the number of nodes in the tree and

DFS Fundamentals

https algomonster s3 us east 2 amazonaws com cover_photos dfs svg Depth First Search Prereqs Recursion Review problems recursion_intro Trees problems tree_intro With a solid understanding of recursion under our belts we are now ready to tackle one of the most useful techniques in coding interviews Depth First Search DFS

BFS Fundamentals

https algomonster s3 us east 2 amazonaws com cover_photos bfs svg Breadth First Search on Trees Hopefully by this time you've drunk enough DFS Kool Aid to understand its immense power and seen enough visualization to create a call stack in your mind Now let me introduce the companion spell

Got a question?ย Ask the Teaching Assistantย anything you don't understand.

Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.

โ†
โ†‘TA ๐Ÿ‘จโ€๐Ÿซ