algoadvance

Leetcode 637. Average of Levels in Binary Tree

Problem Statement

You are given the root of a binary tree. Your task is to find the average value of the nodes on each level in the tree. Return the averages as an array of floating-point numbers.

Clarifying Questions

Before we proceed to the strategy and coding part, let’s clarify a few things:

1. What type of values do the tree nodes store?
   • The problem doesn’t specify any restrictions, but typically, tree nodes will store integers.
2. How should the tree be traversed?
   • Since we need averages level-wise, a level-order traversal (BFS) would be appropriate.
3. What form should the output take?
   • The result should be a vector of doubles representing the average values of each level in the tree.

Strategy

1. Breadth-First Search (BFS) Traversal:
   • Utilize a queue to perform level-order traversal of the tree.
   • For each level, calculate the average of the nodes’ values and store it in a result array.
2. Detailed Steps:
   • Initialize a queue and push the root node onto it.
   • While the queue is not empty, determine the size of the queue (which represents the number of nodes at the current level).
   • Initialize a sum variable for the current level and iterate through all nodes at this level.
   • For each node, add its value to the sum and push its children (if any) onto the queue.
   • Calculate the average for this level and add it to the result vector.
   • Continue this process until all nodes have been processed.

Code

#include <vector>
#include <queue>
#include <cmath>
using namespace std;

// Definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class Solution {
public:
    vector<double> averageOfLevels(TreeNode* root) {
        if (!root) return {};
        
        vector<double> result;
        queue<TreeNode*> q;
        q.push(root);
        
        while (!q.empty()) {
            int size = q.size();
            long sum = 0;  // Using long to handle larger sums without overflow
            
            for (int i = 0; i < size; ++i) {
                TreeNode* node = q.front();
                q.pop();
                sum += node->val;
                if (node->left) q.push(node->left);
                if (node->right) q.push(node->right);
            }
            
            result.push_back(static_cast<double>(sum) / size);
        }
        
        return result;
    }
};

Time Complexity

• Time Complexity: O(N), where N is the number of nodes in the tree. This is because we are visiting each node exactly once during the BFS traversal.
• Space Complexity: O(M), where M is the maximum number of nodes at any level in the queue. In the worst case, this could be O(N/2) which simplifies to O(N) for a balanced tree.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?