Binary Tree Level Order Traversal

🎯

Binary Tree Level Order Traversal

mediumTREEAmazonFacebookMicrosoft

Imagine you want to send a message to everyone in a company, starting from the CEO and moving level by level down the hierarchy. How do you visit each employee in order of their level?

💡 This problem is about traversing a tree level by level, which is different from the usual depth-first traversals beginners often learn first. It can be tricky because you need to process nodes in groups by their depth, not just visit all nodes.

📋

Problem Statement

Given the root of a binary tree, return the level order traversal of its nodes' values. (i.e., from left to right, level by level). Input: root node of a binary tree. Output: a list of lists, where each inner list contains the values of nodes at that level.

The number of nodes in the tree is in the range [1, 10^5].Node values are integers and can be positive, negative, or zero.

💡

Example

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

Output[[3],[9,20],[15,7]]

The root is 3. Level 1 has 3. Level 2 has 9 and 20. Level 3 has 15 and 7.

• Single node tree → [[root_value]]
• Tree with only left children → each level has one node
• Tree with only right children → each level has one node
• Empty tree (null root) → []

⚠️

Common Mistakes

Not handling empty tree input

Code crashes or returns incorrect result

✅ Add check for null root at start

Mixing up level boundaries in BFS loop

Levels merge incorrectly, wrong grouping of nodes

✅ Use level_size variable to process exactly one level at a time

Using recursion without level tracking for level order

Output is not grouped by levels

✅ Pass level parameter and create new list when first visiting level

Using queue.shift() in JavaScript without considering performance

Code runs slower due to O(n) shift operation

✅ Use a proper queue implementation or maintain start index

Forgetting to enqueue children nodes

Traversal incomplete, missing nodes in output

✅ Always check and enqueue left and right children if not null

🧠

Brute Force (Recursive Level Collection)

💡 This approach uses recursion to collect nodes at each level by traversing the tree multiple times. It helps beginners understand the problem from a top-down perspective before learning BFS.

Intuition

We recursively traverse the tree and keep track of the current level. For each node, we add its value to a list corresponding to that level. This requires visiting nodes multiple times to build the final list.

Algorithm

1. Find the height of the tree.
2. For each level from 0 to height-1, recursively collect nodes at that level.
3. Append the collected nodes to the result list.
4. Return the result list after processing all levels.

💡 This algorithm is hard because it requires two passes: one to find height and multiple to collect nodes per level, which is inefficient but conceptually simple.

</>

Code

from typing import List, Optional

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

def height(root: Optional[TreeNode]) -> int:
    if not root:
        return 0
    return 1 + max(height(root.left), height(root.right))

def get_level_nodes(root: Optional[TreeNode], level: int, nodes: List[int]) -> None:
    if not root:
        return
    if level == 0:
        nodes.append(root.val)
    else:
        get_level_nodes(root.left, level - 1, nodes)
        get_level_nodes(root.right, level - 1, nodes)

def levelOrder(root: Optional[TreeNode]) -> List[List[int]]:
    h = height(root)
    result = []
    for i in range(h):
        level_nodes = []
        get_level_nodes(root, i, level_nodes)
        result.append(level_nodes)
    return result

# Example usage:
# root = TreeNode(3, TreeNode(9), TreeNode(20, TreeNode(15), TreeNode(7)))
# print(levelOrder(root))

Line Notes

def height(root: Optional[TreeNode]) -> int:Defines a helper to compute tree height, needed to know how many levels to process

if not root:Base case for empty subtree returns height 0 to stop recursion

return 1 + max(height(root.left), height(root.right))Height is 1 plus the maximum height of left and right subtrees

def get_level_nodes(root: Optional[TreeNode], level: int, nodes: List[int]) -> None:Helper function to collect all nodes at a specific level

if level == 0:If current level matches target level, append node's value to list

get_level_nodes(root.left, level - 1, nodes)Recurse into left subtree decreasing level by 1

get_level_nodes(root.right, level - 1, nodes)Recurse into right subtree decreasing level by 1

for i in range(h):Iterate over all levels from 0 to height-1 to collect nodes level by level

result.append(level_nodes)Add the collected nodes of the current level to the final result list

import java.util.*;

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

public class Solution {
    public int height(TreeNode root) {
        if (root == null) return 0;
        return 1 + Math.max(height(root.left), height(root.right));
    }

    public void getLevelNodes(TreeNode root, int level, List<Integer> nodes) {
        if (root == null) return;
        if (level == 0) nodes.add(root.val);
        else {
            getLevelNodes(root.left, level - 1, nodes);
            getLevelNodes(root.right, level - 1, nodes);
        }
    }

    public List<List<Integer>> levelOrder(TreeNode root) {
        int h = height(root);
        List<List<Integer>> result = new ArrayList<>();
        for (int i = 0; i < h; i++) {
            List<Integer> levelNodes = new ArrayList<>();
            getLevelNodes(root, i, levelNodes);
            result.add(levelNodes);
        }
        return result;
    }

    // Example main
    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.levelOrder(root));
    }
}

Line Notes

public int height(TreeNode root) {Recursively computes the height of the tree to determine number of levels

if (root == null) return 0;Base case returns 0 for null subtree to stop recursion

return 1 + Math.max(height(root.left), height(root.right));Height is 1 plus max height of left and right children

public void getLevelNodes(TreeNode root, int level, List<Integer> nodes) {Helper method to collect nodes at a specific level recursively

if (level == 0) nodes.add(root.val);If current level matches target, add node's value to list

getLevelNodes(root.left, level - 1, nodes);Recurse into left subtree with decremented level

getLevelNodes(root.right, level - 1, nodes);Recurse into right subtree with decremented level

for (int i = 0; i < h; i++) {Iterate over all levels to collect nodes level by level

result.add(levelNodes);Add collected nodes of current level to final result list

public static void main(String[] args) {Driver code to test the solution with example tree

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

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

int height(TreeNode* root) {
    if (!root) return 0;
    return 1 + max(height(root->left), height(root->right));
}

void getLevelNodes(TreeNode* root, int level, vector<int>& nodes) {
    if (!root) return;
    if (level == 0) nodes.push_back(root->val);
    else {
        getLevelNodes(root->left, level - 1, nodes);
        getLevelNodes(root->right, level - 1, nodes);
    }
}

vector<vector<int>> levelOrder(TreeNode* root) {
    int h = height(root);
    vector<vector<int>> result;
    for (int i = 0; i < h; i++) {
        vector<int> levelNodes;
        getLevelNodes(root, i, levelNodes);
        result.push_back(levelNodes);
    }
    return result;
}

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<vector<int>> res = levelOrder(root);
    for (auto &level : res) {
        for (int val : level) cout << val << ' ';
        cout << '\n';
    }
    return 0;
}

Line Notes

int height(TreeNode* root) {Recursive function to compute height of tree for level count

if (!root) return 0;Base case returns 0 for null node to stop recursion

return 1 + max(height(root->left), height(root->right));Height is 1 plus max height of left and right subtrees

void getLevelNodes(TreeNode* root, int level, vector<int>& nodes) {Helper to collect nodes at a specific level recursively

if (level == 0) nodes.push_back(root->val);If current level matches target, add node's value to vector

getLevelNodes(root->left, level - 1, nodes);Recurse into left subtree with decremented level

getLevelNodes(root->right, level - 1, nodes);Recurse into right subtree with decremented level

for (int i = 0; i < h; i++) {Iterate over all levels to collect nodes level by level

result.push_back(levelNodes);Add collected nodes of current level to final result vector

int main() {Driver code to test the function with example tree

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

function height(root) {
    if (!root) return 0;
    return 1 + Math.max(height(root.left), height(root.right));
}

function getLevelNodes(root, level, nodes) {
    if (!root) return;
    if (level === 0) nodes.push(root.val);
    else {
        getLevelNodes(root.left, level - 1, nodes);
        getLevelNodes(root.right, level - 1, nodes);
    }
}

function levelOrder(root) {
    const h = height(root);
    const result = [];
    for (let i = 0; i < h; i++) {
        const levelNodes = [];
        getLevelNodes(root, i, levelNodes);
        result.push(levelNodes);
    }
    return result;
}

// Example usage:
// const root = new TreeNode(3, new TreeNode(9), new TreeNode(20, new TreeNode(15), new TreeNode(7)));
// console.log(levelOrder(root));

Line Notes

function height(root) {Recursively calculates height of tree to determine number of levels

if (!root) return 0;Base case returns 0 for null node to stop recursion

return 1 + Math.max(height(root.left), height(root.right));Height is 1 plus max height of left and right children

function getLevelNodes(root, level, nodes) {Helper function to collect nodes at a specific level recursively

if (level === 0) nodes.push(root.val);If current level matches target, add node's value to array

getLevelNodes(root.left, level - 1, nodes);Recurse into left subtree with decremented level

getLevelNodes(root.right, level - 1, nodes);Recurse into right subtree with decremented level

for (let i = 0; i < h; i++) {Iterate over all levels to collect nodes level by level

result.push(levelNodes);Add collected nodes of current level to final result array

// Example usage:Shows how to test the function with a sample tree

⏱

Complexity

TimeO(n^2)

SpaceO(n)

Height calculation is O(n). For each level, getLevelNodes visits nodes, resulting in O(n) work per level. For a skewed tree height ~ n, total O(n^2).

💡 For n=20, this means roughly 400 operations, which is inefficient for large trees.

Interview Verdict: Use only to introduce - not efficient for large inputs

This approach is too slow for big trees but helps understand level order traversal conceptually.

🧠

Better Approach (BFS with Queue)

💡 This approach uses a queue to traverse the tree level by level in a single pass, which is more efficient and intuitive once you understand BFS.

Intuition

Use a queue to process nodes in FIFO order. At each iteration, process all nodes currently in the queue (one level), then enqueue their children for the next level.

Algorithm

1. Initialize a queue and add the root node.
2. While the queue is not empty, get the number of nodes at the current level.
3. Process each node at this level: dequeue, add its value to a list, enqueue its children.
4. Add the list of current level nodes to the result.
5. Return the result after processing all levels.

💡 This algorithm is easier to follow because it processes nodes level by level in one pass without recursion.

</>

Code

from typing import List, Optional
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 levelOrder(root: Optional[TreeNode]) -> List[List[int]]:
    if not root:
        return []
    result = []
    queue = deque([root])
    while queue:
        level_size = len(queue)
        level_nodes = []
        for _ in range(level_size):
            node = queue.popleft()
            level_nodes.append(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        result.append(level_nodes)
    return result

# Example usage:
# root = TreeNode(3, TreeNode(9), TreeNode(20, TreeNode(15), TreeNode(7)))
# print(levelOrder(root))

Line Notes

if not root:Handle empty tree edge case immediately to avoid processing

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

while queue:Process nodes level by level until queue is empty

level_size = len(queue)Number of nodes at current level to process exactly

for _ in range(level_size):Process all nodes at current level to maintain grouping

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

if node.left:Enqueue left child if it exists for next level processing

if node.right:Enqueue right child if it exists for next level processing

result.append(level_nodes)Add current level's collected node values to result

import java.util.*;

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

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

    // Example main
    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.levelOrder(root));
    }
}

Line Notes

if (root == null) return result;Return empty list immediately if tree is empty

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

queue.offer(root);Add root node to queue to start traversal

while (!queue.isEmpty()) {Process nodes level by level until queue is empty

int levelSize = queue.size();Number of nodes at current level to process exactly

for (int i = 0; i < levelSize; i++) {Process all nodes at current level to maintain grouping

TreeNode node = queue.poll();Remove node from front of queue for processing

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

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

result.add(levelNodes);Add current level's collected node values to result list

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

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

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

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<vector<int>> res = levelOrder(root);
    for (auto &level : res) {
        for (int val : level) cout << val << ' ';
        cout << '\n';
    }
    return 0;
}

Line Notes

if (!root) return result;Return empty result immediately if tree is empty

queue<TreeNode*> q;Queue to hold nodes for BFS traversal

q.push(root);Add root node to queue to start traversal

while (!q.empty()) {Process nodes level by level until queue is empty

int levelSize = q.size();Number of nodes at current level to process exactly

for (int i = 0; i < levelSize; i++) {Process all nodes at current level to maintain grouping

TreeNode* node = q.front();Get front node from queue for processing

q.pop();Remove node from queue after processing

if (node->left) q.push(node->left);Enqueue left child if it exists for next level

if (node->right) q.push(node->right);Enqueue right child if it exists for next level

result.push_back(levelNodes);Add current level's collected node values to result vector

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

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

// Example usage:
// const root = new TreeNode(3, new TreeNode(9), new TreeNode(20, new TreeNode(15), new TreeNode(7)));
// console.log(levelOrder(root));

Line Notes

if (!root) return [];Return empty array immediately if tree is empty

const queue = [root];Initialize queue with root node to start BFS traversal

while (queue.length > 0) {Process nodes level by level until queue is empty

const levelSize = queue.length;Number of nodes at current level to process exactly

for (let i = 0; i < levelSize; i++) {Process all nodes at current level to maintain grouping

const node = queue.shift();Remove first node from queue for processing (note: shift is O(n) in arrays)

if (node.left) queue.push(node.left);Enqueue left child if it exists for next level

if (node.right) queue.push(node.right);Enqueue right child if it exists for next level

result.push(levelNodes);Add current level's collected node values to result array

// Example usage:Shows how to test the function with a sample tree

⏱

Complexity

TimeO(n)

SpaceO(n)

Each node is enqueued and dequeued exactly once, so time is O(n). The queue can hold up to O(n) nodes in worst case (full last level).

💡 For n=20, this means about 20 operations, which is very efficient.

Interview Verdict: Accepted - optimal for this problem

This is the standard approach to code in interviews for level order traversal.

🧠

Alternative Approach (DFS with Level Tracking)

💡 This approach uses DFS recursion but tracks the level to build the result list. It combines recursion with level order output and is useful to understand different traversal styles.

Intuition

Traverse the tree depth-first, but pass the current level as a parameter. Append node values to the list corresponding to their level, creating new lists as needed.

Algorithm

1. Initialize an empty result list.
2. Define a recursive helper that takes a node and its level.
3. If the current level does not exist in result, add a new list.
4. Append the node's value to the list for its level.
5. Recursively call helper for left and right children with level + 1.
6. Return the result after traversal.

💡 This algorithm is elegant but requires careful level tracking and dynamic list creation.

</>

Code

from typing import List, Optional

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

def dfs_level_order(root: Optional[TreeNode]) -> List[List[int]]:
    result = []
    def dfs(node: Optional[TreeNode], level: int):
        if not node:
            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

# Example usage:
# root = TreeNode(3, TreeNode(9), TreeNode(20, TreeNode(15), TreeNode(7)))
# print(dfs_level_order(root))

Line Notes

result = []Initialize result list to hold nodes grouped by level

def dfs(node: Optional[TreeNode], level: int):Recursive helper function with current node and its level

if not node:Base case: return if node is null to stop recursion

if level == len(result):If first time visiting this level, add a new list to result

result[level].append(node.val)Append current node's value to its corresponding level list

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

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

import java.util.*;

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

public class Solution {
    public List<List<Integer>> dfsLevelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        dfs(root, 0, result);
        return result;
    }

    private void dfs(TreeNode node, int level, List<List<Integer>> result) {
        if (node == null) return;
        if (level == result.size()) result.add(new ArrayList<>());
        result.get(level).add(node.val);
        dfs(node.left, level + 1, result);
        dfs(node.right, level + 1, result);
    }

    // Example main
    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.dfsLevelOrder(root));
    }
}

Line Notes

List<List<Integer>> result = new ArrayList<>();Initialize result list to hold nodes grouped by level

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

if (node == null) return;Base case: return if node is null to stop recursion

if (level == result.size()) result.add(new ArrayList<>());Add new list if first time visiting this level

result.get(level).add(node.val);Append current node's value to its level list

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

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

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

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

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

vector<vector<int>> dfsLevelOrder(TreeNode* root) {
    vector<vector<int>> result;
    dfs(root, 0, result);
    return result;
}

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<vector<int>> res = dfsLevelOrder(root);
    for (auto &level : res) {
        for (int val : level) cout << val << ' ';
        cout << '\n';
    }
    return 0;
}

Line Notes

void dfs(TreeNode* node, int level, vector<vector<int>>& result) {Recursive DFS helper with current node and level

if (!node) return;Base case: return if node is null to stop recursion

if (level == result.size()) result.push_back(vector<int>());Add new vector if first time visiting this level

result[level].push_back(node->val);Append current node's value to its level vector

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

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

vector<vector<int>> dfsLevelOrder(TreeNode* root) {Main function to start DFS and return result

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

function dfsLevelOrder(root) {
    const result = [];
    function dfs(node, level) {
        if (!node) return;
        if (level === result.length) result.push([]);
        result[level].push(node.val);
        dfs(node.left, level + 1);
        dfs(node.right, level + 1);
    }
    dfs(root, 0);
    return result;
}

// Example usage:
// const root = new TreeNode(3, new TreeNode(9), new TreeNode(20, new TreeNode(15), new TreeNode(7)));
// console.log(dfsLevelOrder(root));

Line Notes

const result = [];Initialize array to hold nodes grouped by level

function dfs(node, level) {Recursive helper function with current node and level

if (!node) return;Base case: return if node is null to stop recursion

if (level === result.length) result.push([]);Add new array if first time visiting this level

result[level].push(node.val);Append current node's value to its level array

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

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

⏱

Complexity

TimeO(n)

SpaceO(n)

Each node is visited once in DFS. The result list stores all nodes, so space is O(n).

💡 For n=20, this means about 20 operations, similar to BFS but using recursion.

Interview Verdict: Accepted - alternative to BFS

This approach is elegant and accepted but BFS is more common for level order traversal.

📊

All Approaches - One-Glance Tradeoffs

💡 In interviews, the BFS queue approach is the best to code due to clarity and efficiency.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force (Recursive Level Collection)	O(n^2)	O(n)	Yes (deep recursion for height and level collection)	N/A	Mention only - never code due to inefficiency
2. BFS with Queue	O(n)	O(n)	No	N/A	Code this approach in 95% of interviews
3. DFS with Level Tracking	O(n)	O(n)	Yes (deep recursion possible)	N/A	Mention as alternative; code if comfortable with recursion

💼

Interview Strategy

💡 Use this guide to understand the problem deeply before interviews. Start by clarifying the problem, then explain the brute force approach to show understanding, followed by the optimal BFS solution. Practice coding and testing edge cases.

How to Present

Clarify input and output format, including empty tree case.State the brute force recursive approach to show understanding of levels.Explain the BFS queue approach as the optimal solution.Optionally mention DFS with level tracking as an alternative.Write clean code and test with sample and edge cases.

Time Allocation

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

What the Interviewer Tests

Interviewer tests your understanding of tree traversal, ability to use queues for BFS, handling of edge cases, and clean code writing.

Common Follow-ups

• How to do zigzag level order traversal? → Alternate direction per level.
• How to find average of nodes at each level? → Sum values per level and divide by count.

💡 These follow-ups test your ability to modify BFS for variations and aggregate computations.

🔍

Pattern Recognition

When to Use

1) Input is a tree or graph, 2) Output requires nodes grouped by distance or level, 3) Problem mentions 'level order' or 'breadth-first', 4) Need to process nodes layer by layer.

Signature Phrases

level order traversalnodes at each levelbreadth-first search

NOT This Pattern When

Depth-first traversals like inorder, preorder, postorder - these do not group nodes by level.

Similar Problems

Binary Tree Zigzag Level Order Traversal - similar BFS with alternating orderN-ary Tree Level Order Traversal - BFS on trees with multiple children

Practice

1. Given the following code for the right side view of a binary tree, what is the final output when run on this tree? Tree structure: - Root = 1 - Root.left = 2 - Root.right = 3 - Root.left.right = 5 - Root.right.right = 4

from typing import Optional, List
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

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.right, depth + 1)
        dfs(node.left, depth + 1)
    dfs(root, 0)
    return rightside

print(rightSideView(root))  # What is printed?

easy

A. [1, 3, 5]

B. [1, 2, 5]

C. [1, 3, 4]

D. [1, 2, 4]

Solution

1. Step 1: Trace dfs at depth 0

   Start at root (1), depth=0, rightside is empty, so append 1.

2. Step 2: Traverse right subtree first

   At depth=1, visit node 3, append 3 since rightside length=1. Then visit node 4 at depth=2, append 4.

3. Step 3: Traverse left subtree

   At depth=1, node 2 is visited but depth=1 already in rightside, so skip append. Node 5 at depth=2 is skipped since depth=2 already in rightside.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Output matches expected right side view [OK]

Hint: Right-first DFS appends first node per depth [OK]

Common Mistakes:

• Appending left nodes at same depth overwrites right nodes
• Confusing order of traversal causing wrong nodes appended
• Off-by-one errors in depth indexing

2. You are given a binary tree and need to count nodes that are "good" -- nodes whose value is greater than or equal to all values on the path from the root to that node. Which algorithmic approach guarantees an optimal solution for this problem?

easy

A. A greedy traversal that counts nodes greater than their immediate parent only

B. Depth-first search (DFS) or breadth-first search (BFS) that tracks the maximum value seen on the path to each node

C. Dynamic programming with memoization storing counts for subtrees

D. Sorting nodes by value and then counting based on sorted order

Solution

1. Step 1: Understand the problem requirement

   The problem requires comparing each node's value to all values on the path from the root, not just its parent.

2. Step 2: Identify the approach that tracks path state

   Only DFS or BFS that carries the maximum value seen so far on the path can correctly determine if a node is "good".

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Tracking max value on path ensures correct counting [OK]

Hint: Track max value on path, not just parent [OK]

Common Mistakes:

• Only compare node to parent, missing path max
• Trying DP without path state
• Sorting nodes loses tree structure

3. Consider the following code snippet for checking if a binary tree is symmetric using BFS. Given the tree with root value 1, left child 2, right child 2, left child's left child 3, and right child's right child 3, what is the return value of the function?

easy

A. True

B. False

C. Raises an exception due to None handling

D. Infinite loop

Solution

1. Step 1: Trace initial queue and first iteration

   Queue starts with [root, root] (both value 1). Both nodes are equal, enqueue their children pairs: (2,2) and (2,2).

2. Step 2: Trace second iteration and subsequent checks

   Next pairs are (2,2) and (2,2). Values match, enqueue their children pairs: (3,None) and (None,3). The None checks pass because left of one matches right of the other.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   All mirrored pairs match, so function returns True [OK]

Hint: Mirrored nodes with matching values and structure return True [OK]

Common Mistakes:

• Confusing left-left with left-right children in queue
• Missing None checks causing exceptions
• Assuming asymmetry due to None children mismatch

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

5. Consider this buggy BFS code for finding largest values in each tree row:

def largestValues(root):
    if not root:
        return []
    res = []
    queue = deque([root])
    while queue:
        level_max = float('-inf')
        for _ in range(len(queue)):
            node = queue.popleft()
            level_max = max(level_max, node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        res.append(level_max)
    return res

What subtle bug could cause incorrect results when running multiple test cases in the same environment?

medium

A. Not resetting the queue between test cases causing leftover nodes to be processed

B. Appending level_max before processing all nodes at the current level

C. Forgetting to check if node.left or node.right is None before appending

D. Using a global variable for res without clearing it before each call

Solution

1. Step 1: Identify use of global variables

   If res is declared globally and not cleared before each call, results accumulate across tests.

2. Step 2: Confirm other lines are correct

   Queue is local and reset per call; children are checked for None; level_max appended after level processed.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Global res not cleared -> incorrect cumulative results [OK]

Hint: Global variables must be reset between test runs [OK]

Common Mistakes:

• Forgetting to clear global or static variables
• Assuming local variables persist incorrectly
• Misunderstanding queue initialization scope