637.Average of Levels in Binary Tree

📘 LeetCode 637: Average of Levels in Binary Tree

📌 Problem Overview

• Problem Number: 637
• Problem Name: Average of Levels in Binary Tree
• Difficulty: Easy
• Category: Trees
• Runnable Source: Program.cs

---

💡 Algorithmic Approach & Pattern

This problem is solved using the Trees algorithmic pattern.

Key Insights & Invariants:

1. Identify the input constraints and edge conditions.
2. Structure the data flow to minimize unnecessary traversals and heap reallocations.
3. Validate corner cases (empty collections, single-element cases, duplicates, extremes).

---

💻 Verified C# Implementation (.NET 9)

The solution is verified and executable via the companion project in src/637.Average-of-Levels-in-Binary-Tree/:

Console.WriteLine(string.Join(", ", AverageOfLevels(new(1, new(2), new(3)))));
Console.WriteLine(string.Join(", ", AverageOfLevels(new(2147483647, new(2147483647), new(2147483647)))));
Console.WriteLine(string.Join(", ", AverageOfLevels(new(1, new(2, new(3, new(4)))))));
Console.WriteLine(string.Join(", ", AverageOfLevels(new(1, new(2, new(4), new(5)), new(3, new(6), new(7))))));
Console.WriteLine(string.Join(", ", AverageOfLevels(new(10, null, new(20, null, new(30, null, new(40)))))));
 
IList<double> AverageOfLevels(TreeNode root)
{
   if (root == null)
      return [];
 
   var queue = new Queue<TreeNode>();
   var result = new List<double>();
   queue.Enqueue(root); 
   while (queue.Count > 0)
   {
      double size = queue.Count;
      double len = size;
      double sum = 0;
      while (size > 0)
      {
         TreeNode n = queue.Dequeue();
         size--;
         sum += n.val;
         if (n.left != null) queue.Enqueue(n.left);
         if (n.right != null) queue.Enqueue(n.right);
      }
      result.Add((double)sum / len);
   }
   return result;
}
 
//   Definition for a binary tree node.
public class TreeNode
{
   public int val;
   public TreeNode left;
   public TreeNode right;
   public TreeNode(int val = 0, TreeNode? left = null, TreeNode? right = null)
   {
      this.val = val;
      this.left = left;
      this.right = right;
   }
}

---

📊 Complexity Analysis

Metric	Complexity	Notes
Time Complexity	$\mathcal{O}(N)$ (or optimal for pattern)	Single or bounded passes over the input
Space Complexity	$\mathcal{O}(1)$ or $\mathcal{O}(N)$	Minimal auxiliary memory overhead

---

🚨 Edge Cases & Interview Traps

• Empty / Null Input: Ensure null safety and guard clauses.
• Single Element: Confirm the algorithm terminates without out-of-bounds indexing.
• Duplicates & Boundaries: Check duplicate handling and extreme integer limits.