Average of Levels in Binary Tree

Apple Interview Question

Problem Overview

Difficulty: Easy
LeetCode Pattern: BFS

Given the root of a binary tree, return the average value of the nodes on each level in the form of an array.

Input:
  3
 / \
9   20
   /  \
  15   7

Output:
· [3.00,14.50,11.00]

---

Step 1: Clarify Requirements

• Can the tree be empty?

  • Yes, it can be empty.

  • Return empty list in that case.

• Can node values be negative?

  • Yes, values can be negative.

• Should the output preserve the tree level order?

  • Yes, output should be level by level from top to bottom.

---

Step 2: Discuss Approaches

1/ BFS Level Order (Optimal ✅)

• Logic:

  • Use a queue for BFS

  • For each level:

    • Sum all node values

    • Count nodes

    • Compute average

  • Add average to result list

  • Repeat for all levels

• Big O:

  • Time Complexity: O(n)

  • Space Complexity: O(n)

---

2/ DFS with Level Tracking (Alternative ✅)

• Logic:

  • Traverse tree using DFS

  • Keep track of:

    • level sums

    • counts

  • After traversal:

    • compute average for each level

• Big O:

  • Time Complexity: O(n)

  • Space Complexity: O(h)

---

Step 3: Write Code (Optimal)

Python

---

Java

---

C++

---

Step 4: Answer Follow-Ups

• What if the tree is empty?

  • Return an empty list [].

• What if tree is very deep?

  • DFS can cause stack overflow.

  • Using BFS is a better choice.

• What if node values are very large?

  • Use double/float to avoid overflow.