Average of Levels in Binary Tree

📋

Problem

Imagine you are analyzing a company's organizational chart represented as a binary tree, and you want to find the average salary at each level of management.

Given a non-empty binary tree, return the average value of the nodes on each level in the form of an array. The average value of a level is the sum of the node values divided by the number of nodes at that level.

The number of nodes in the tree is in the range [1, 10^5].Node values are integers in the range [-10^5, 10^5].

Edge cases: Single node tree → average is the node's valueTree with all nodes having the same value → averages equal that valueTree with negative and positive values → averages reflect correct signed values

</>

IDE

def averageOfLevels(root: Optional[TreeNode]) -> List[float]:public List<Double> averageOfLevels(TreeNode root)vector<double> averageOfLevels(TreeNode* root)function averageOfLevels(root)

def averageOfLevels(root):
    # Write your solution here
    pass

class Solution {
    public List<Double> averageOfLevels(TreeNode root) {
        // Write your solution here
        return new ArrayList<>();
    }
}

#include <vector>
using namespace std;

vector<double> averageOfLevels(TreeNode* root) {
    // Write your solution here
    return {};
}

function averageOfLevels(root) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: [3, 14, 11]Integer division truncation causing loss of decimal averages.✅ Use floating point division when computing averages: level_sum / level_count as float.

Wrong: []Not handling the base case when root is not null but no children exist.✅ Return [root.val] when root has no children instead of empty list.

Wrong: [1.0, 2.0]Not processing all nodes at the last level, missing nodes in BFS queue processing.✅ Process exactly the number of nodes at each level before moving to next level.

Wrong: Timeout or no outputUsing DFS without level tracking or repeated traversals causing O(n^2) complexity.✅ Implement BFS with queue to achieve O(n) time complexity.

✓

Test Cases

Try testing your code on trees with only one node or all nodes equal.

Consider skewed trees and complete trees to catch subtle bugs.

Test your solution on large inputs to ensure it runs efficiently.

t1_01basic

Input{"root":[3,9,20,null,null,15,7]}

Expected[3,14.5,11]

⏱ Performance - must finish in 2000ms

Level 0 has one node with value 3, average = 3. Level 1 has nodes 9 and 20, average = (9+20)/2 = 14.5. Level 2 has nodes 15 and 7, average = (15+7)/2 = 11.

💡 Use a queue to traverse the tree level by level.

💡 At each level, sum node values and divide by the number of nodes at that level.

💡 Append the average to the result list after processing each level.

Why it failed: Incorrect averages due to not summing all nodes per level or incorrect division. Fix by summing all node values at each level and dividing by the count of nodes at that level.

✓ Correctly computes averages for each level using BFS.

t1_02basic

Input{"root":[1,2,3,4,5,6,7]}

Expected[1,2.5,5.5]

⏱ Performance - must finish in 2000ms

Level 0: [1], average=1. Level 1: [2,3], average=(2+3)/2=2.5. Level 2: [4,5,6,7], average=(4+5+6+7)/4=5.5.

💡 Traverse the tree level by level using a queue.

💡 Calculate sum and count of nodes at each level before averaging.

💡 Remember to process all nodes at the current level before moving to the next.

Why it failed: Failing to process all nodes at a level or mixing nodes from different levels causes wrong averages. Fix by using a loop that processes exactly the current level's node count.

✓ Correctly handles multiple levels and computes averages.

t2_01edge

Input{"root":[10]}

Expected[10]

⏱ Performance - must finish in 2000ms

Single node tree; average is the node's value itself.

💡 Check how your code handles a tree with only one node.

💡 Ensure the average calculation does not divide by zero or miss the single node.

💡 Return a list with the single node's value as a float.

Why it failed: Code returns empty list or incorrect average for single node tree. Fix by handling the base case where root is not null and has no children.

✓ Correctly returns average for single node tree.

t2_02edge

Input{"root":[5,5,5,5,5,5,5]}

Expected[5,5,5]

⏱ Performance - must finish in 2000ms

All nodes have the same value 5; averages at all levels equal 5.

💡 Test if your code correctly sums identical values at each level.

💡 Check that division by count does not alter the expected identical average.

💡 Ensure no integer division truncation if using integer types.

Why it failed: Averages differ from node values due to integer division or incorrect summation. Fix by using floating point division and summing all nodes per level.

✓ Correctly computes averages when all node values are identical.

t2_03edge

Input{"root":[1,-1,1,-1,null,null,1]}

Expected[1,0,0]

⏱ Performance - must finish in 2000ms

Level 0: [1], average=1. Level 1: [−1,1], average=0. Level 2: [−1,1], average=0.

💡 Verify your code handles negative and positive values correctly.

💡 Sum values carefully without losing sign information.

💡 Use floating point division to get correct averages including zero.

Why it failed: Incorrect averages due to ignoring negative values or integer division truncation. Fix by summing signed integers and using floating point division.

✓ Correctly computes averages with mixed positive and negative values.

t3_01corner

Input{"root":[1,2,null,3,null,4,null,5]}

Expected[1,2,3,4,5]

⏱ Performance - must finish in 2000ms

Tree with only left children; each level has one node, average equals node value.

💡 Check if your BFS correctly handles levels with only one node.

💡 Ensure the queue updates correctly when only one child exists per node.

💡 Process each level fully even if width is 1.

Why it failed: Code fails to handle skewed trees with single child nodes per level, causing missing levels or wrong averages. Fix by correctly enqueueing existing children and processing all nodes per level.

✓ Correctly computes averages for skewed trees with single children.

t3_02corner

Input{"root":[1,null,2,null,3,null,4,null,5]}

Expected[1,2,3,4,5]

⏱ Performance - must finish in 2000ms

Tree with only right children; each level has one node, average equals node value.

💡 Verify BFS handles right-only child trees correctly.

💡 Make sure null children do not cause errors or skipped levels.

💡 Process all nodes at each level even if only one node exists.

Why it failed: Code incorrectly skips levels or fails on right-only child trees due to null checks. Fix by properly checking and enqueueing right children only if they exist.

✓ Correctly computes averages for right-skewed trees.

t3_03corner

Input{"root":[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15]}

Expected[1,2.5,5.5,11.5]

⏱ Performance - must finish in 2000ms

Complete binary tree with 4 levels; averages computed correctly per level.

💡 Check if your code correctly counts nodes at each level in a complete tree.

💡 Ensure no off-by-one errors in level node count or sum.

💡 Use a loop that processes exactly the current level's node count.

Why it failed: Off-by-one errors cause incorrect averages or missing nodes at last level. Fix by using a fixed loop for the current level's node count before moving to next level.

✓ Correctly computes averages for complete binary trees.

t4_01performance

Input{"root":[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100]}

Expectednull

⏱ Performance - must finish in 2000ms

Large tree with 100 nodes; BFS O(n) must complete within 2 seconds.

💡 Use BFS with a queue to achieve O(n) time complexity.

💡 Avoid unnecessary recomputations or data structure overhead.

💡 Process each node exactly once to maintain linear time.

Why it failed: Algorithm exceeds time limit due to non-linear complexity or repeated traversals. Fix by implementing BFS with a queue and processing each node once.

✓ Algorithm runs within time limit using O(n) BFS traversal.

Practice

1. Consider the following Python code implementing the optimal DFS approach for bottom-up level order traversal. What is the final output when run on the given tree?

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def levelOrderBottom(root):
    levels = []
    def dfs(node, level):
        if not node:
            return
        if len(levels) == level:
            levels.append([])
        levels[level].append(node.val)
        dfs(node.left, level + 1)
        dfs(node.right, level + 1)
    dfs(root, 0)
    return levels[::-1]

root = TreeNode(3)
root.left = TreeNode(9)
root.right = TreeNode(20, TreeNode(15), TreeNode(7))
print(levelOrderBottom(root))

easy

A. [[15, 7], [9, 20], [3]]

B. [[3], [9, 20], [15, 7]]

C. [[9, 20], [3], [15, 7]]

D. [[15, 7], [3], [9, 20]]

Solution

1. Step 1: Trace dfs calls and levels

   Level 0: [3], Level 1: [9, 20], Level 2: [15, 7]

2. Step 2: Reverse levels list before returning

   Reversing [[3], [9, 20], [15, 7]] yields [[15, 7], [9, 20], [3]]

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Output matches bottom-up level order traversal [OK]

Hint: Remember to reverse levels collected by DFS [OK]

Common Mistakes:

• Forgetting to reverse levels
• Mixing up left and right children order

2. You are given a binary tree and need to find the maximum width among all levels. The width is defined as the length between the end-nodes (the leftmost and rightmost non-null nodes), including null nodes in between. Which approach guarantees an optimal solution for this problem?

easy

A. Use BFS with indexing of nodes to track their positions and normalize indices at each level to avoid overflow.

B. Perform a simple level order traversal counting only non-null nodes at each level and take the maximum count.

C. Use DFS to traverse the tree and track the minimum and maximum node indices at each depth to compute width.

D. Apply a greedy approach that always picks the widest subtree at each node to estimate maximum width.

Solution

1. Step 1: Understand the problem constraints

   The width includes null nodes between end-nodes, so counting only non-null nodes per level underestimates width.

2. Step 2: Identify the approach that tracks positions

   BFS with indexing assigns position indices to nodes, allowing calculation of width as the difference between first and last indices at each level. Normalizing indices prevents integer overflow on deep trees.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Indexing with normalization handles sparse trees and deep levels correctly [OK]

Hint: Index nodes with BFS and normalize indices [OK]

Common Mistakes:

• Counting only non-null nodes per level
• Using DFS without proper indexing
• Ignoring index normalization causing overflow

3. You are given a binary tree and need to determine if it is symmetric around its center. Which approach best guarantees an optimal solution by comparing nodes in pairs using a queue and terminating early when asymmetry is detected?

easy

A. Recursive depth-first traversal comparing left subtree to left subtree

B. Dynamic programming storing subtree symmetry states bottom-up

C. Greedy traversal checking only the root and immediate children

D. Iterative breadth-first search using a queue to compare mirrored node pairs with early termination

Solution

1. Step 1: Understand the problem requirement

   The problem requires checking if a tree is symmetric, which means the left subtree is a mirror reflection of the right subtree.

2. Step 2: Identify the approach that compares mirrored nodes efficiently

   Using an iterative BFS with a queue to compare pairs of nodes from left and right subtrees simultaneously allows early detection of asymmetry and avoids unnecessary traversal.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Iterative BFS with paired nodes and early termination is optimal for symmetry check [OK]

Hint: Symmetry requires mirrored node pair comparison [OK]

Common Mistakes:

• Comparing left subtree to left subtree instead of mirrored right subtree
• Using greedy checks that miss deeper asymmetry
• Assuming symmetry can be checked by root and immediate children only

4. Consider the following buggy code snippet for connecting next right pointers in a perfect binary tree. Which line contains the subtle bug that can cause incorrect next pointer connections?

medium

A. Line: head.left.next = head.right

B. Line: if head.next:

C. Line: leftmost = leftmost.left

D. Line: head.right.next = head.next.right

Solution

1. Step 1: Compare the buggy line with the correct logic

   The correct connection is head.right.next = head.next.left, but here it uses head.next.right, which is incorrect.

2. Step 2: Understand the impact

   This causes right child's next pointer to point to the wrong node, breaking the chain.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Right child's next must connect to next node's left child [OK]

Hint: Right child's next points to next node's left child [OK]

Common Mistakes:

• Confusing next.left and next.right
• Skipping null checks
• Not updating leftmost pointer

5. Suppose the vertical order traversal problem is extended so that nodes can appear multiple times if they have the same column and row but different parents (e.g., in a graph-like structure with shared nodes). Which modification to the BFS with column tracking approach correctly handles this scenario?

hard

A. Modify BFS to track (node, column, row) and store nodes in a list keyed by (column, row), then sort by parent ID

B. Use DFS with sorting by column, row, and parent to order nodes

C. Use BFS with column tracking but ignore row and parent, just append nodes as visited

D. Use BFS with column tracking and a visited set to avoid revisiting nodes

Solution

1. Step 1: Understand problem extension

   Nodes can appear multiple times if they share column and row but differ by parent, so row and parent info must be tracked.

2. Step 2: Evaluate modifications

   Tracking (node, column, row) and sorting by parent ID ensures correct ordering. Ignoring row or parent loses correctness. Visited set prevents duplicates but may skip valid repeats.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Tracking row and parent allows correct ordering of duplicates [OK]

Hint: Track row and parent to distinguish duplicates in BFS [OK]

Common Mistakes:

• Ignoring row or parent info leads to incorrect grouping
• Using visited set that skips valid repeated nodes