Average of Levels in Binary Tree

🎯

Average of Levels in Binary Tree

easyTREEAmazonFacebook

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.

💡 This problem requires understanding how to traverse a tree level by level and aggregate values at each level. Beginners often struggle with managing the traversal order and correctly grouping nodes by their depth.

📋

Problem Statement

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].

💡

Example

Input"root = [3,9,20,null,null,15,7]"

Output[3.0, 14.5, 11.0]

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.

• Single node tree → average is the node's value
• Tree with all nodes having the same value → averages equal that value
• Tree with negative and positive values → averages reflect correct signed values
• Tree with only left or only right children → averages computed correctly per level

⚠️

Common Mistakes

Not separating nodes by level correctly

Averages are incorrect because nodes from different levels are mixed

✅ Use queue size before processing each level to isolate nodes per level

Integer division instead of floating point division

Averages are truncated to integers, losing precision

✅ Cast numerator or denominator to float/double before division

Not handling empty tree input

Code crashes or returns incorrect result

✅ Check if root is null/None before processing

Using recursion without level tracking in DFS

Cannot aggregate values per level correctly

✅ Pass level parameter in DFS calls and use arrays indexed by level

Modifying queue while iterating without fixing level size

Infinite loops or incorrect level grouping

✅ Store queue size at start of level processing and iterate exactly that many times

🧠

Brute Force (Level Order Traversal with Queue)

💡 This approach introduces the fundamental BFS traversal to process nodes level by level, which is essential to understand before optimizing.

Intuition

Traverse the tree level by level using a queue, sum the values at each level, and then compute the average by dividing by the number of nodes at that level.

Algorithm

1. Initialize a queue and add the root node.
2. While the queue is not empty, process all nodes currently in the queue (one level).
3. Sum their values and count the nodes to compute the average for that level.
4. Add their children to the queue for the next level and repeat.

💡 The challenge is to correctly separate nodes by levels using the queue size before processing each level.

</>

Code

from collections import deque

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

def averageOfLevels(root):
    if not root:
        return []
    result = []
    queue = deque([root])
    while queue:
        level_sum = 0
        level_count = len(queue)
        for _ in range(level_count):
            node = queue.popleft()
            level_sum += node.val
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        result.append(level_sum / level_count)
    return result

# Example usage:
# root = TreeNode(3, TreeNode(9), TreeNode(20, TreeNode(15), TreeNode(7)))
# print(averageOfLevels(root))  # Output: [3.0, 14.5, 11.0]

Line Notes

from collections import dequeImport deque for efficient queue operations

if not root:Handle empty tree edge case early

queue = deque([root])Initialize queue with root to start BFS

level_count = len(queue)Determine number of nodes at current level

for _ in range(level_count):Process exactly one level's nodes

node = queue.popleft()Pop node from front of queue for processing

level_sum += node.valAccumulate sum of node values at this level

if node.left:Add left child to queue for next level if exists

if node.right:Add right child to queue for next level if exists

result.append(level_sum / level_count)Compute and store average for current level

import java.util.*;

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int val) { this.val = val; }
}

public class Solution {
    public List<Double> averageOfLevels(TreeNode root) {
        List<Double> result = new ArrayList<>();
        if (root == null) return result;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int levelCount = queue.size();
            double levelSum = 0;
            for (int i = 0; i < levelCount; i++) {
                TreeNode node = queue.poll();
                levelSum += node.val;
                if (node.left != null) queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
            }
            result.add(levelSum / levelCount);
        }
        return result;
    }

    // Example usage:
    // public static void main(String[] args) {
    //     TreeNode root = new TreeNode(3);
    //     root.left = new TreeNode(9);
    //     root.right = new TreeNode(20);
    //     root.right.left = new TreeNode(15);
    //     root.right.right = new TreeNode(7);
    //     Solution sol = new Solution();
    //     System.out.println(sol.averageOfLevels(root));
    // }
}

Line Notes

List<Double> result = new ArrayList<>();Prepare list to store averages per level

if (root == null) return result;Handle empty tree edge case

Queue<TreeNode> queue = new LinkedList<>();Initialize queue for BFS traversal

queue.offer(root);Start BFS with root node

int levelCount = queue.size();Number of nodes at current level

for (int i = 0; i < levelCount; i++)Process all nodes at this level

TreeNode node = queue.poll();Retrieve and remove node from queue

levelSum += node.val;Sum node values for average calculation

if (node.left != null) queue.offer(node.left);Add left child for next level

if (node.right != null) queue.offer(node.right);Add right child for next level

result.add(levelSum / levelCount);Calculate and store average for this level

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left, *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

vector<double> averageOfLevels(TreeNode* root) {
    vector<double> result;
    if (!root) return result;
    queue<TreeNode*> q;
    q.push(root);
    while (!q.empty()) {
        int levelCount = q.size();
        double levelSum = 0;
        for (int i = 0; i < levelCount; i++) {
            TreeNode* node = q.front();
            q.pop();
            levelSum += node->val;
            if (node->left) q.push(node->left);
            if (node->right) q.push(node->right);
        }
        result.push_back(levelSum / levelCount);
    }
    return result;
}

// Example usage:
// int main() {
//     TreeNode* root = new TreeNode(3);
//     root->left = new TreeNode(9);
//     root->right = new TreeNode(20);
//     root->right->left = new TreeNode(15);
//     root->right->right = new TreeNode(7);
//     vector<double> averages = averageOfLevels(root);
//     for (double avg : averages) cout << avg << " ";
//     cout << endl;
//     return 0;
// }

Line Notes

vector<double> result;Store averages for each level

if (!root) return result;Handle empty tree case

queue<TreeNode*> q;Queue for BFS traversal

q.push(root);Start BFS with root node

int levelCount = q.size();Count nodes at current level

for (int i = 0; i < levelCount; i++)Process all nodes at this level

TreeNode* node = q.front();Access front node in queue

q.pop();Remove node after processing

levelSum += node->val;Sum node values for average

if (node->left) q.push(node->left);Add left child for next level

if (node->right) q.push(node->right);Add right child for next level

result.push_back(levelSum / levelCount);Calculate and store average

class TreeNode {
    constructor(val=0, left=null, right=null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

function averageOfLevels(root) {
    if (!root) return [];
    const result = [];
    const queue = [root];
    while (queue.length > 0) {
        let levelSum = 0;
        const levelCount = queue.length;
        for (let i = 0; i < levelCount; i++) {
            const node = queue.shift();
            levelSum += node.val;
            if (node.left) queue.push(node.left);
            if (node.right) queue.push(node.right);
        }
        result.push(levelSum / levelCount);
    }
    return result;
}

// Example usage:
// const root = new TreeNode(3, new TreeNode(9), new TreeNode(20, new TreeNode(15), new TreeNode(7)));
// console.log(averageOfLevels(root)); // Output: [3.0, 14.5, 11.0]

Line Notes

if (!root) return [];Handle empty tree edge case

const queue = [root];Initialize queue with root node

const levelCount = queue.length;Number of nodes at current level

for (let i = 0; i < levelCount; i++)Process all nodes at this level

const node = queue.shift();Remove node from front of queue

levelSum += node.val;Accumulate sum of node values

if (node.left) queue.push(node.left);Add left child for next level

if (node.right) queue.push(node.right);Add right child for next level

result.push(levelSum / levelCount);Compute and store average for current level

⏱

Complexity

TimeO(n)

SpaceO(w) where w is the maximum width of the tree

Each node is visited exactly once, and the queue holds at most the maximum number of nodes at any level.

💡 For n=1000 nodes, this means roughly 1000 operations, which is efficient for interview constraints.

Interview Verdict: Accepted

This approach is efficient and accepted for the problem constraints, making it a solid baseline solution.

🧠

DFS with Level Tracking

💡 This approach uses depth-first traversal but keeps track of levels to aggregate sums and counts, offering an alternative to BFS.

Intuition

Traverse the tree recursively, passing the current level as a parameter, and accumulate sums and counts in arrays indexed by level.

Algorithm

1. Initialize two arrays: one for sum of values per level, one for count of nodes per level.
2. Define a recursive DFS function that takes a node and its level.
3. At each node, add its value to the sum array and increment the count array for that level.
4. Recursively call DFS on left and right children with level + 1.
5. After traversal, compute averages by dividing sums by counts for each level.

💡 The key is correctly passing and using the level parameter to aggregate data per depth.

</>

Code

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

def averageOfLevels(root):
    sums = []
    counts = []
    def dfs(node, level):
        if not node:
            return
        if level == len(sums):
            sums.append(0)
            counts.append(0)
        sums[level] += node.val
        counts[level] += 1
        dfs(node.left, level + 1)
        dfs(node.right, level + 1)
    dfs(root, 0)
    return [s / c for s, c in zip(sums, counts)]

# Example usage:
# root = TreeNode(3, TreeNode(9), TreeNode(20, TreeNode(15), TreeNode(7)))
# print(averageOfLevels(root))  # Output: [3.0, 14.5, 11.0]

Line Notes

sums = []Initialize list to store sum of values per level

counts = []Initialize list to store count of nodes per level

def dfs(node, level):Recursive DFS function with level tracking

if level == len(sums):Detect first visit to this level to initialize sums and counts

sums[level] += node.valAdd current node's value to sum for this level

counts[level] += 1Increment count of nodes at this level

dfs(node.left, level + 1)Recurse left child with incremented level

dfs(node.right, level + 1)Recurse right child with incremented level

return [s / c for s, c in zip(sums, counts)]Compute averages after traversal

import java.util.*;

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int val) { this.val = val; }
}

public class Solution {
    List<Double> result = new ArrayList<>();
    List<Long> sums = new ArrayList<>();
    List<Integer> counts = new ArrayList<>();

    public List<Double> averageOfLevels(TreeNode root) {
        dfs(root, 0);
        for (int i = 0; i < sums.size(); i++) {
            result.add(sums.get(i) * 1.0 / counts.get(i));
        }
        return result;
    }

    private void dfs(TreeNode node, int level) {
        if (node == null) return;
        if (level == sums.size()) {
            sums.add(0L);
            counts.add(0);
        }
        sums.set(level, sums.get(level) + node.val);
        counts.set(level, counts.get(level) + 1);
        dfs(node.left, level + 1);
        dfs(node.right, level + 1);
    }

    // Example usage:
    // public static void main(String[] args) {
    //     TreeNode root = new TreeNode(3);
    //     root.left = new TreeNode(9);
    //     root.right = new TreeNode(20);
    //     root.right.left = new TreeNode(15);
    //     root.right.right = new TreeNode(7);
    //     Solution sol = new Solution();
    //     System.out.println(sol.averageOfLevels(root));
    // }
}

Line Notes

List<Long> sums = new ArrayList<>();Store sum of node values per level using long to avoid overflow

List<Integer> counts = new ArrayList<>();Store count of nodes per level

public List<Double> averageOfLevels(TreeNode root)Main function to return averages

dfs(root, 0);Start DFS traversal from root at level 0

if (level == sums.size())Initialize sums and counts for new level

sums.set(level, sums.get(level) + node.val);Add node value to sum at current level

counts.set(level, counts.get(level) + 1);Increment count at current level

dfs(node.left, level + 1);Recurse left child with incremented level

dfs(node.right, level + 1);Recurse right child with incremented level

result.add(sums.get(i) * 1.0 / counts.get(i));Calculate average for each level

#include <iostream>
#include <vector>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left, *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

void dfs(TreeNode* node, int level, vector<long long>& sums, vector<int>& counts) {
    if (!node) return;
    if (level == sums.size()) {
        sums.push_back(0);
        counts.push_back(0);
    }
    sums[level] += node->val;
    counts[level]++;
    dfs(node->left, level + 1, sums, counts);
    dfs(node->right, level + 1, sums, counts);
}

vector<double> averageOfLevels(TreeNode* root) {
    vector<double> result;
    vector<long long> sums;
    vector<int> counts;
    dfs(root, 0, sums, counts);
    for (int i = 0; i < sums.size(); i++) {
        result.push_back((double)sums[i] / counts[i]);
    }
    return result;
}

// Example usage:
// int main() {
//     TreeNode* root = new TreeNode(3);
//     root->left = new TreeNode(9);
//     root->right = new TreeNode(20);
//     root->right->left = new TreeNode(15);
//     root->right->right = new TreeNode(7);
//     vector<double> averages = averageOfLevels(root);
//     for (double avg : averages) cout << avg << " ";
//     cout << endl;
//     return 0;
// }

Line Notes

void dfs(TreeNode* node, int level, vector<long long>& sums, vector<int>& counts)DFS helper with level tracking and reference to sums and counts

if (level == sums.size())Initialize sums and counts for new level

sums[level] += node->val;Add node value to sum at current level

counts[level]++;Increment count of nodes at this level

dfs(node->left, level + 1, sums, counts);Recurse left child with incremented level

dfs(node->right, level + 1, sums, counts);Recurse right child with incremented level

for (int i = 0; i < sums.size(); i++)Compute averages after traversal

result.push_back((double)sums[i] / counts[i]);Store average for each level

class TreeNode {
    constructor(val=0, left=null, right=null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

function averageOfLevels(root) {
    const sums = [];
    const counts = [];
    function dfs(node, level) {
        if (!node) return;
        if (level === sums.length) {
            sums.push(0);
            counts.push(0);
        }
        sums[level] += node.val;
        counts[level] += 1;
        dfs(node.left, level + 1);
        dfs(node.right, level + 1);
    }
    dfs(root, 0);
    return sums.map((sum, i) => sum / counts[i]);
}

// Example usage:
// const root = new TreeNode(3, new TreeNode(9), new TreeNode(20, new TreeNode(15), new TreeNode(7)));
// console.log(averageOfLevels(root)); // Output: [3.0, 14.5, 11.0]

Line Notes

const sums = [];Array to accumulate sums per level

const counts = [];Array to count nodes per level

function dfs(node, level)Recursive DFS with level parameter

if (level === sums.length)Initialize sums and counts for new level

sums[level] += node.val;Add node value to sum for current level

counts[level] += 1;Increment count for current level

dfs(node.left, level + 1);Recurse left child with incremented level

dfs(node.right, level + 1);Recurse right child with incremented level

return sums.map((sum, i) => sum / counts[i]);Compute averages after traversal

⏱

Complexity

TimeO(n)

SpaceO(h) where h is the height of the tree due to recursion stack plus O(h) for sums and counts

Each node is visited once in DFS; sums and counts arrays grow with tree height.

💡 For a balanced tree with height ~log n, this uses less memory than BFS queue in wide trees.

Interview Verdict: Accepted

This approach is also efficient and accepted, offering a recursive alternative to BFS.

🧠

Optimized BFS with Running Average Calculation

💡 This approach optimizes memory usage by calculating the running average on the fly without storing sums separately.

Intuition

While traversing each level with BFS, maintain a running sum and count, then compute the average immediately before moving to the next level.

Algorithm

1. Initialize a queue with the root node.
2. For each level, initialize sum and count to zero.
3. Process all nodes at the current level, updating sum and count.
4. Compute the average immediately and append to result.
5. Add children of current level nodes to the queue for next level.

💡 This approach is similar to the brute force BFS but emphasizes computing averages immediately to save space.

</>

Code

from collections import deque

def averageOfLevels(root):
    if not root:
        return []
    result = []
    queue = deque([root])
    while queue:
        level_sum = 0
        level_count = len(queue)
        for _ in range(level_count):
            node = queue.popleft()
            level_sum += node.val
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        result.append(level_sum / level_count)
    return result

# Example usage:
# root = TreeNode(3, TreeNode(9), TreeNode(20, TreeNode(15), TreeNode(7)))
# print(averageOfLevels(root))  # Output: [3.0, 14.5, 11.0]

Line Notes

if not root:Handle empty tree edge case

queue = deque([root])Initialize BFS queue with root

level_count = len(queue)Number of nodes at current level

for _ in range(level_count):Process all nodes at this level

node = queue.popleft()Pop node from queue for processing

level_sum += node.valAccumulate sum for current level

if node.left:Add left child for next level

if node.right:Add right child for next level

result.append(level_sum / level_count)Compute and store average immediately

import java.util.*;

public class Solution {
    public List<Double> averageOfLevels(TreeNode root) {
        List<Double> result = new ArrayList<>();
        if (root == null) return result;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int levelCount = queue.size();
            double levelSum = 0;
            for (int i = 0; i < levelCount; i++) {
                TreeNode node = queue.poll();
                levelSum += node.val;
                if (node.left != null) queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
            }
            result.add(levelSum / levelCount);
        }
        return result;
    }

    // Example usage:
    // public static void main(String[] args) {
    //     TreeNode root = new TreeNode(3);
    //     root.left = new TreeNode(9);
    //     root.right = new TreeNode(20);
    //     root.right.left = new TreeNode(15);
    //     root.right.right = new TreeNode(7);
    //     Solution sol = new Solution();
    //     System.out.println(sol.averageOfLevels(root));
    // }
}

Line Notes

if (root == null) return result;Handle empty tree

Queue<TreeNode> queue = new LinkedList<>();Initialize queue for BFS

queue.offer(root);Start BFS with root node

int levelCount = queue.size();Count nodes at current level

for (int i = 0; i < levelCount; i++)Process all nodes at this level

TreeNode node = queue.poll();Retrieve node from queue

levelSum += node.val;Sum node values for average

if (node.left != null) queue.offer(node.left);Add left child for next level

if (node.right != null) queue.offer(node.right);Add right child for next level

result.add(levelSum / levelCount);Calculate and store average immediately

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

vector<double> averageOfLevels(TreeNode* root) {
    vector<double> result;
    if (!root) return result;
    queue<TreeNode*> q;
    q.push(root);
    while (!q.empty()) {
        int levelCount = q.size();
        double levelSum = 0;
        for (int i = 0; i < levelCount; i++) {
            TreeNode* node = q.front();
            q.pop();
            levelSum += node->val;
            if (node->left) q.push(node->left);
            if (node->right) q.push(node->right);
        }
        result.push_back(levelSum / levelCount);
    }
    return result;
}

// Example usage:
// int main() {
//     TreeNode* root = new TreeNode(3);
//     root->left = new TreeNode(9);
//     root->right = new TreeNode(20);
//     root->right->left = new TreeNode(15);
//     root->right->right = new TreeNode(7);
//     vector<double> averages = averageOfLevels(root);
//     for (double avg : averages) cout << avg << " ";
//     cout << endl;
//     return 0;
// }

Line Notes

if (!root) return result;Handle empty tree case

queue<TreeNode*> q;Initialize queue for BFS

q.push(root);Start BFS with root node

int levelCount = q.size();Number of nodes at current level

for (int i = 0; i < levelCount; i++)Process all nodes at this level

TreeNode* node = q.front();Access front node in queue

q.pop();Remove node after processing

levelSum += node->val;Sum node values for average

if (node->left) q.push(node->left);Add left child for next level

if (node->right) q.push(node->right);Add right child for next level

result.push_back(levelSum / levelCount);Calculate and store average immediately

function averageOfLevels(root) {
    if (!root) return [];
    const result = [];
    const queue = [root];
    while (queue.length > 0) {
        let levelSum = 0;
        const levelCount = queue.length;
        for (let i = 0; i < levelCount; i++) {
            const node = queue.shift();
            levelSum += node.val;
            if (node.left) queue.push(node.left);
            if (node.right) queue.push(node.right);
        }
        result.push(levelSum / levelCount);
    }
    return result;
}

// Example usage:
// const root = new TreeNode(3, new TreeNode(9), new TreeNode(20, new TreeNode(15), new TreeNode(7)));
// console.log(averageOfLevels(root)); // Output: [3.0, 14.5, 11.0]

Line Notes

if (!root) return [];Handle empty tree edge case

const queue = [root];Initialize queue with root node

const levelCount = queue.length;Number of nodes at current level

for (let i = 0; i < levelCount; i++)Process all nodes at this level

const node = queue.shift();Remove node from front of queue

levelSum += node.val;Accumulate sum of node values

if (node.left) queue.push(node.left);Add left child for next level

if (node.right) queue.push(node.right);Add right child for next level

result.push(levelSum / levelCount);Compute and store average immediately

⏱

Complexity

TimeO(n)

SpaceO(w) where w is the maximum width of the tree

Same as brute force BFS, but averages computed immediately to avoid extra storage.

💡 This approach is memory efficient and suitable for large trees with wide levels.

Interview Verdict: Accepted

This is the preferred BFS approach in interviews due to its clarity and efficiency.

📊

All Approaches - One-Glance Tradeoffs

💡 The optimized BFS approach is recommended for most interviews due to clarity and efficiency.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force BFS	O(n)	O(w)	No	N/A	Good to mention and code as baseline
2. DFS with Level Tracking	O(n)	O(h)	Yes (deep trees)	N/A	Good alternative to show recursive skills
3. Optimized BFS with Running Average	O(n)	O(w)	No	N/A	Preferred approach to code in interviews

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice coding all approaches, and prepare to explain tradeoffs clearly in interviews.

How to Present

Clarify the problem and constraints with the interviewer.Start with the brute force BFS approach to show understanding of level order traversal.Discuss the DFS alternative to demonstrate recursive thinking.Present the optimized BFS with immediate average calculation as the best practical solution.Write clean, tested code and explain your reasoning throughout.

Time Allocation

Clarify: 2min → Approach: 3min → Code: 10min → Test: 5min. Total ~20min

What the Interviewer Tests

Interviewer tests your understanding of BFS and DFS tree traversals, ability to aggregate data per level, and code clarity and correctness.

Common Follow-ups

• What if the tree is very deep? → Use DFS with recursion limit or iterative DFS.
• Can you do this without extra space? → No, at least O(w) space is needed for BFS queue.
• How to handle floating point precision? → Use double/float and be aware of rounding.
• What if nodes have non-integer values? → Same approach applies with floating point sums.

💡 These follow-ups test your robustness and understanding of edge cases and constraints beyond the basic problem.

🔍

Pattern Recognition

When to Use

Use this pattern when you need to process or aggregate data level-by-level in a tree or graph.

Signature Phrases

'average value of the nodes on each level''level order traversal''nodes on the same depth'

NOT This Pattern When

This is not a DFS path sum or subtree aggregation problem, which require different traversal and aggregation logic.

Similar Problems

Binary Tree Level Order Traversal - returns nodes per level instead of averagesMaximum Level Sum of a Binary Tree - finds max sum per level instead of averageFind Largest Value in Each Tree Row - finds max value per level

Practice

1. Given a binary tree, you need to return the values of its nodes level by level starting from the bottom-most level up to the root. Which algorithmic approach guarantees an optimal solution for this problem?

easy

A. Perform a standard level order traversal (BFS) and then reverse the collected levels at the end.

B. Use a depth-first search (DFS) with level tracking to collect nodes per level, then reverse the levels after traversal.

C. Apply a greedy approach by always visiting the right child before the left child to get bottom-up order.

D. Use dynamic programming to store subtrees' bottom-up levels and merge them.

Solution

1. Step 1: Understand problem requirements

   The problem requires collecting nodes level by level from bottom to top, which is not a simple BFS traversal order.

2. Step 2: Identify approach that naturally collects levels bottom-up

   Performing a standard BFS collects nodes level by level from top to bottom. Reversing the collected levels at the end yields the bottom-up order efficiently and straightforwardly.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   BFS with reversal is optimal and simple [OK]

Hint: Bottom-up levels are easiest with BFS and reversal [OK]

Common Mistakes:

• Assuming DFS alone gives bottom-up order without reversal
• Using greedy traversal order incorrectly

2. Consider this buggy Python code for DFS-based level order traversal. Which line contains the subtle bug that causes incorrect grouping of nodes by level?

def dfs_level_order(root: Optional[TreeNode]) -> List[List[int]]:
    result = []
    def dfs(node: Optional[TreeNode], level: int):
        if node is None:
            return
        if level == len(result):
            result.append([])
        result[level].append(node.val)
        dfs(node.left, level + 1)
        dfs(node.right, level + 1)
    dfs(root, 0)
    return result

medium

A. Line calling dfs on left child: 'dfs(node.left, level + 1)'

B. Line checking if node is null: 'if node is null: return'

C. Line appending node value: 'result[level].append(node.val)'

D. Line checking if level < len(result): 'if level < len(result): result.append([])'

Solution

1. Step 1: Analyze condition for appending new level list

   The condition should be 'if level == len(result)' to append a new list when first visiting that level.

2. Step 2: Identify effect of incorrect condition

   Using 'level < len(result)' causes appending a new list when the level already exists, leading to incorrect grouping and index errors.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Condition must check equality, not less than [OK]

Hint: Check if level equals result length before appending [OK]

Common Mistakes:

• Using wrong comparison operator in level check
• Ignoring empty tree case
• Mixing left and right child calls

3. Identify the bug in the following code snippet for the right side view of a binary tree:

def rightSideView(root: Optional[TreeNode]) -> List[int]:
    rightside = []
    def dfs(node, depth):
        if not node:
            return
        if depth == len(rightside):
            rightside.append(node.val)
        dfs(node.left, depth + 1)  # Line X
        dfs(node.right, depth + 1) # Line Y
    dfs(root, 0)
    return rightside

Which line contains the bug causing incorrect right side view?

medium

A. Line with 'if depth == len(rightside): rightside.append(node.val)'

B. Line X: 'dfs(node.left, depth + 1)'

C. Line Y: 'dfs(node.right, depth + 1)'

D. Line with 'if not node: return'

Solution

1. Step 1: Understand traversal order

   The code visits left child before right child, so left nodes are appended first at each depth.

2. Step 2: Why this causes bug

   Visiting left first causes left nodes to be recorded as visible, overwriting right nodes that should be visible from the right side.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Swapping left and right child calls fixes the bug [OK]

Hint: Right-first DFS needed to capture rightmost nodes [OK]

Common Mistakes:

• Visiting left child before right in DFS causes wrong nodes appended
• Appending nodes without checking depth length
• Not handling null nodes properly

4. The following code attempts to perform vertical order traversal using BFS and column tracking. Identify the line containing the subtle bug that causes incorrect grouping of nodes by column.

from collections import deque
from sortedcontainers import SortedDict

def verticalOrder(root):
    if not root:
        return []
    col_table = SortedDict()
    queue = deque([(root, 0)])
    while queue:
        node, col = queue.popleft()
        if col in col_table:
            col_table[col] = []  # Bug here
        col_table[col].append(node.val)
        if node.left:
            queue.append((node.left, col - 1))
        if node.right:
            queue.append((node.right, col + 1))
    return list(col_table.values())

medium

A. Line: if not root: return []

B. Line: if col in col_table: col_table[col] = []

C. Line: queue.append((node.left, col - 1))

D. Line: queue = deque([(root, 0)])

Solution

1. Step 1: Analyze col_table initialization

   The condition resets col_table[col] to empty list if col already exists, erasing previous nodes in that column.

2. Step 2: Understand impact on output

   This causes nodes in the same column to be overwritten, breaking vertical grouping.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Correct code initializes list only if col not in col_table [OK]

Hint: Resetting list on existing key erases previous nodes [OK]

Common Mistakes:

• Confusing 'if col not in col_table' with 'if col in col_table'
• Not initializing column list properly

5. The following code attempts to find the minimum depth of a binary tree using recursion. Identify the bug that causes incorrect results when one child is missing.

def minDepth(root):
    if not root:
        return 0
    if not root.left and not root.right:
        return 1
    left_depth = minDepth(root.left)
    right_depth = minDepth(root.right)
    return min(left_depth, right_depth) + 1

medium

A. Line 3: base case for leaf nodes is incorrect

B. Line 5: missing check for null root

C. Line 6: min() used without checking if one child is null

D. Line 7: missing +1 to account for current node

Solution

1. Step 1: Understand the bug with missing children

   If one child is null, minDepth returns 0 for that side, causing min() to pick 0 incorrectly.

2. Step 2: Why this causes wrong minimum depth

   Using min() blindly returns 1 instead of the correct depth from the non-null child, underestimating depth.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Bug is in min() usage without null child check -> incorrect depth [OK]

Hint: min() on zero from null child causes wrong depth [OK]

Common Mistakes:

• Assuming min() works without null checks
• Confusing min and max for depth calculation
• Ignoring base cases for leaf nodes