637. Average of Levels in Binary Tree LeetCode Solution

In this guide, you will get 637. Average of Levels in Binary Tree LeetCode Solution with the best time and space complexity. The solution to Average of Levels in Binary Tree problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Average of Levels in Binary Tree solution in C++
Average of Levels in Binary Tree solution in Java
Average of Levels in Binary Tree solution in Python
Additional Resources

637. Average of Levels in Binary Tree LeetCode Solution image

Problem Statement of Average of Levels in Binary Tree

Given the root of a binary tree, return the average value of the nodes on each level in the form of an array. Answers within 10-5 of the actual answer will be accepted.

Example 1:

Input: root = [3,9,20,null,null,15,7]
Output: [3.00000,14.50000,11.00000]
Explanation: The average value of nodes on level 0 is 3, on level 1 is 14.5, and on level 2 is 11.
Hence return [3, 14.5, 11].

Example 2:

Input: root = [3,9,20,15,7]
Output: [3.00000,14.50000,11.00000]

Constraints:

The number of nodes in the tree is in the range [1, 104].
-231 <= Node.val <= 231 – 1

Complexity Analysis

Time Complexity:
Space Complexity:

637. Average of Levels in Binary Tree LeetCode Solution in C++

class Solution {
 public:
  vector<double> averageOfLevels(TreeNode* root) {
    vector<double> ans;
    queue<TreeNode*> q{{root}};

    while (!q.empty()) {
      long sum = 0;
      const int size = q.size();
      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);
      }
      ans.push_back(sum / (double)size);
    }

    return ans;
  }
};
/* code provided by PROGIEZ */

637. Average of Levels in Binary Tree LeetCode Solution in Java

class Solution {
  public List<Double> averageOfLevels(TreeNode root) {
    List<Double> ans = new ArrayList<>();
    Queue<TreeNode> q = new ArrayDeque<>(List.of(root));

    while (!q.isEmpty()) {
      long sum = 0;
      final int size = q.size();
      for (int i = 0; i < size; ++i) {
        TreeNode node = q.poll();
        sum += node.val;
        if (node.left != null)
          q.offer(node.left);
        if (node.right != null)
          q.offer(node.right);
      }
      ans.add(sum / (double) size);
    }

    return ans;
  }
}
// code provided by PROGIEZ