Average of Levels in Binary Tree - Solution & Explanation

Problem Overview: You are given the root of a binary tree and need to compute the average value of nodes at every depth level. The result should return one average per level, starting from the root and moving downward.

Approach 1: Breadth-First Search (BFS) Using Queue (Time: O(n), Space: O(w))

This approach performs a level-order traversal using a queue. Push the root into the queue, then repeatedly process nodes level by level. For each level, track the number of nodes currently in the queue, iterate through them, accumulate their values, and push their children into the queue. After processing the level, compute the average as levelSum / levelSize and append it to the result list. BFS naturally groups nodes by depth, making it the most straightforward way to compute per-level aggregates in a breadth-first search traversal.

This method visits every node exactly once, giving O(n) time complexity where n is the number of nodes in the tree. Space complexity is O(w), where w is the maximum width of the tree (the largest number of nodes at any level). For balanced trees, this can approach O(n). In practice, BFS is usually the clearest and most interview-friendly solution for problems that require level-based processing.

Approach 2: Depth-First Search (DFS) With Pre-order Traversal (Time: O(n), Space: O(h))

The DFS solution uses recursion to traverse the tree while tracking the current depth. Maintain two arrays (or lists): one storing the cumulative sum of values per level and another storing the count of nodes per level. During a depth-first search, whenever you visit a node, check whether the current depth already exists in the arrays. If not, initialize it. Then update the sum and increment the node count for that level.

After the traversal completes, compute each level's average by dividing the stored sum by the count. The traversal itself still touches every node once, resulting in O(n) time complexity. Space complexity is O(h) for the recursion stack, where h is the height of the tree, plus the arrays that store level sums and counts. DFS works well when recursion feels more natural or when you want tighter control over traversal logic in a binary tree.

Recommended for interviews: The BFS queue solution is typically what interviewers expect first because the problem explicitly asks for level-based results. It maps directly to level-order traversal and keeps the implementation simple. Showing the DFS variant demonstrates deeper understanding of tree traversal patterns and how to aggregate values across recursion levels.