Binary Tree Level Order Traversal II (Bottom-Up)

🎯

Binary Tree Level Order Traversal II (Bottom-Up)

mediumTREEAmazonGoogle

Imagine you are analyzing a company's organizational chart from the bottom-most employees up to the CEO, and you want to list employees level by level starting from the lowest level.

💡 This problem requires traversing a binary tree level by level but returning the levels in reverse order (bottom-up). Beginners often struggle because they are used to top-down level order traversal and may not immediately see how to reverse the order efficiently.

📋

Problem Statement

Given the root of a binary tree, return the bottom-up level order traversal of its nodes' values. (i.e., from left to right, level by level from leaf to root). Input is the root node of the binary tree. Output is a list of lists of integers representing node values at each level, starting from the bottom level.

The number of nodes in the tree is in the range [0, 10^4].-1000 <= Node.val <= 1000

💡

Example

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

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

The tree has three levels. The bottom level has nodes 15 and 7, the middle level has 9 and 20, and the top level has 3. We return levels from bottom to top.

• Empty tree → []
• Tree with only root → [[root.val]]
• Tree with only left children → levels reversed accordingly
• Tree with only right children → levels reversed accordingly

⚠️

Common Mistakes

Not separating nodes by levels correctly

All nodes get mixed in one list, losing level order

✅ Use a queue size variable to process nodes level by level

Reversing the result incorrectly or forgetting to reverse

Output is top-down instead of bottom-up

✅ Reverse the list of levels before returning or insert levels at front

Using inefficient list insertion at front with arrays

Performance degrades due to O(n) insertions

✅ Use linked list structures or reverse at the end instead

Not handling empty tree input

Code may crash or return null instead of empty list

✅ Check if root is null and return empty list early

Stack overflow in DFS for very deep trees

Program crashes due to too deep recursion

✅ Use BFS approach or iterative DFS with stack

🧠

Brute Force (Level Order then Reverse)

💡 This approach uses a straightforward BFS to collect levels top-down, then reverses the result at the end. It helps beginners understand level order traversal before optimizing.

Intuition

Perform a normal level order traversal collecting nodes level by level from top to bottom, then reverse the collected list to get bottom-up order.

Algorithm

1. Initialize a queue and add the root node if not null.
2. While the queue is not empty, process nodes level by level.
3. For each level, collect all node values in a list.
4. After traversal, reverse the list of levels and return it.

💡 The main challenge is to correctly separate nodes by levels and then reverse the final list to meet the bottom-up requirement.

</>

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 levelOrderBottom(root):
    if not root:
        return []
    queue = deque([root])
    result = []
    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[::-1]

# Example usage:
if __name__ == '__main__':
    root = TreeNode(3)
    root.left = TreeNode(9)
    root.right = TreeNode(20, TreeNode(15), TreeNode(7))
    print(levelOrderBottom(root))

Line Notes

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

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

while queue:Process nodes level by level until no nodes remain.

for _ in range(level_size):Iterate exactly over current level nodes to separate levels.

result.append(level_nodes)Collect current level nodes before moving to next level.

return result[::-1]Reverse the collected levels to get bottom-up order.

import java.util.*;

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

public class Solution {
    public List<List<Integer>> levelOrderBottom(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);
        }
        Collections.reverse(result);
        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.levelOrderBottom(root));
    }
}

Line Notes

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

Queue<TreeNode> queue = new LinkedList<>();Use queue to perform BFS traversal.

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

result.add(levelNodes);Add current level's nodes to result list.

Collections.reverse(result);Reverse the list to get bottom-up order.

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

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

vector<vector<int>> levelOrderBottom(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);
    }
    reverse(result.begin(), result.end());
    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 = levelOrderBottom(root);
    for (auto &level : res) {
        for (int val : level) cout << val << ' ';
        cout << '\n';
    }
    return 0;
}

Line Notes

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

queue<TreeNode*> q;Queue for BFS traversal of tree nodes.

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

result.push_back(levelNodes);Store current level's node values.

reverse(result.begin(), result.end());Reverse levels to get bottom-up order.

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

function levelOrderBottom(root) {
    if (!root) return [];
    const queue = [root];
    const result = [];
    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.reverse();
}

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

Line Notes

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

const queue = [root];Initialize queue with root node for BFS.

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

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

return result.reverse();Reverse the collected levels to get bottom-up order.

⏱

Complexity

TimeO(n)

SpaceO(n)

We visit each node once during BFS, and store all nodes in the result. Reversing the list is O(n) as well.

💡 For n=10,000 nodes, this means roughly 10,000 operations to traverse and store nodes, plus 10,000 to reverse the list, which is efficient enough.

Interview Verdict: Accepted

This approach is efficient and accepted, making it a solid baseline solution for interviews.

🧠

Better (Prepend Levels During BFS)

💡 Instead of collecting levels top-down and reversing at the end, we insert each level at the front of the result list during BFS. This avoids the reversal step and is more direct.

Intuition

As we process each level from top to bottom, insert the level's nodes at the beginning of the result list so the final list is bottom-up without extra reversal.

Algorithm

1. Initialize a queue with the root node if not null.
2. While the queue is not empty, process nodes level by level.
3. Collect all node values for the current level.
4. Insert the current level's list at the front of the result list.

💡 The key difference is inserting at the front instead of appending, which changes the order naturally.

</>

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 levelOrderBottom(root):
    if not root:
        return []
    queue = deque([root])
    result = []
    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.insert(0, level_nodes)
    return result

# Example usage:
if __name__ == '__main__':
    root = TreeNode(3)
    root.left = TreeNode(9)
    root.right = TreeNode(20, TreeNode(15), TreeNode(7))
    print(levelOrderBottom(root))

Line Notes

if not root:Handle empty tree edge case early.

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

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

for _ in range(level_size):Process all nodes at current level.

result.insert(0, level_nodes)Insert current level at front to build bottom-up order.

import java.util.*;

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

public class Solution {
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        LinkedList<List<Integer>> result = new LinkedList<>();
        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.addFirst(levelNodes);
        }
        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.levelOrderBottom(root));
    }
}

Line Notes

LinkedList<List<Integer>> result = new LinkedList<>();Use LinkedList to efficiently add levels at front.

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

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

result.addFirst(levelNodes);Insert current level at front to build bottom-up order.

#include <iostream>
#include <vector>
#include <queue>
#include <list>

using namespace std;

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

vector<vector<int>> levelOrderBottom(TreeNode* root) {
    list<vector<int>> tempResult;
    if (!root) return {};
    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);
        }
        tempResult.push_front(levelNodes);
    }
    return vector<vector<int>>(tempResult.begin(), tempResult.end());
}

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

Line Notes

list<vector<int>> tempResult;Use list to efficiently insert levels at front.

if (!root) return {};Return empty vector if tree is empty.

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

tempResult.push_front(levelNodes);Insert current level at front to build bottom-up order.

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

function levelOrderBottom(root) {
    if (!root) return [];
    const queue = [root];
    const result = [];
    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.unshift(levelNodes);
    }
    return result;
}

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

Line Notes

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

const queue = [root];Initialize queue with root node for BFS.

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

result.unshift(levelNodes);Insert current level at front to build bottom-up order.

⏱

Complexity

TimeO(n)

SpaceO(n)

We still visit each node once, but avoid the reversal step by inserting at front, which is O(1) for linked lists or O(n) for arrays but acceptable here.

💡 For n=10,000 nodes, this saves the reversal step, making the approach slightly more direct and elegant.

Interview Verdict: Accepted

This approach is a neat optimization over the brute force and is often preferred in interviews.

🧠

Optimal (DFS with Level Tracking and Post-Processing)

💡 This approach uses DFS to collect nodes by level, then reverses the collected levels at the end. It shows an alternative to BFS and helps understand tree traversal depth-first.

Intuition

Perform a DFS traversal, passing the current level as a parameter. Append node values to a list corresponding to their level. After traversal, reverse the list of levels to get bottom-up order.

Algorithm

1. Initialize an empty list of lists to hold nodes per level.
2. Define a recursive DFS function that takes a node and its level.
3. If the current level list doesn't exist, create it.
4. Append the node's value to its level list.
5. Recursively call DFS on left and right children with level+1.
6. After DFS completes, reverse the list of levels and return.

💡 The challenge is managing the level parameter and ensuring lists exist for each level before appending.

</>

Code

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]

# Example usage:
if __name__ == '__main__':
    root = TreeNode(3)
    root.left = TreeNode(9)
    root.right = TreeNode(20, TreeNode(15), TreeNode(7))
    print(levelOrderBottom(root))

Line Notes

levels = []Initialize list to hold nodes per level.

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

if len(levels) == level:Create new list for this level if it doesn't exist.

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

return levels[::-1]Reverse levels to get bottom-up order.

import java.util.*;

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

public class Solution {
    List<List<Integer>> levels = new ArrayList<>();

    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        dfs(root, 0);
        Collections.reverse(levels);
        return levels;
    }

    private void dfs(TreeNode node, int level) {
        if (node == null) return;
        if (levels.size() == level) {
            levels.add(new ArrayList<>());
        }
        levels.get(level).add(node.val);
        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.levelOrderBottom(root));
    }
}

Line Notes

List<List<Integer>> levels = new ArrayList<>();Store nodes grouped by level.

if (levels.size() == level) {Create new list for current level if needed.

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

Collections.reverse(levels);Reverse levels to get bottom-up order.

#include <iostream>
#include <vector>
#include <algorithm>

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<vector<int>>& levels) {
    if (!node) return;
    if (levels.size() == level) {
        levels.push_back(vector<int>());
    }
    levels[level].push_back(node->val);
    dfs(node->left, level + 1, levels);
    dfs(node->right, level + 1, levels);
}

vector<vector<int>> levelOrderBottom(TreeNode* root) {
    vector<vector<int>> levels;
    dfs(root, 0, levels);
    reverse(levels.begin(), levels.end());
    return levels;
}

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

Line Notes

if (levels.size() == level) {Create new vector for current level if it doesn't exist.

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

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

reverse(levels.begin(), levels.end());Reverse levels to get bottom-up order.

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

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

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

Line Notes

const levels = [];Initialize array to hold nodes per level.

function dfs(node, level) {Recursive DFS with level tracking.

if (levels.length === level) {Create new array for current level if needed.

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

return levels.reverse();Reverse levels to get bottom-up order.

⏱

Complexity

TimeO(n)

SpaceO(n)

DFS visits each node once, storing values by level. Reversing the levels is O(n).

💡 For n=10,000 nodes, this approach is as efficient as BFS but uses recursion which may affect stack space.

Interview Verdict: Accepted

This approach is a good alternative to BFS and shows mastery of DFS with level tracking.

📊

All Approaches - One-Glance Tradeoffs

💡 In most interviews, approach 2 (BFS with prepending) is the best balance of clarity and efficiency to code quickly.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force (Level Order then Reverse)	O(n)	O(n)	No	N/A	Good to mention and implement first.
2. Better (Prepend Levels During BFS)	O(n)	O(n)	No	N/A	Preferred approach to code in interviews.
3. Optimal (DFS with Level Tracking and Post-Processing)	O(n)	O(n)	Yes (deep trees)	N/A	Good alternative; discuss if interviewer asks for DFS.

💼

Interview Strategy

💡 Use this guide to understand the problem deeply before interviews. Start by clarifying the problem, then explain the brute force approach, and progressively optimize. Practice coding and testing each approach.

How to Present

Step 1: Clarify the problem and constraints with the interviewer.Step 2: Describe the brute force BFS approach and implement it.Step 3: Suggest optimization by inserting levels at the front during BFS.Step 4: Optionally, discuss DFS with level tracking as an alternative.Step 5: Test your code with edge cases and explain complexity.

Time Allocation

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

What the Interviewer Tests

The interviewer tests your understanding of BFS and DFS tree traversals, ability to handle level separation, and how you optimize and explain your solution.

Common Follow-ups

• How would you do this without reversing the list at the end? → Insert levels at front during BFS.
• Can you solve this using DFS? → Use recursion with level tracking and reverse at the end.

💡 These follow-ups test your flexibility with traversal methods and your ability to optimize space/time.

🔍

Pattern Recognition

When to Use

1. Need to traverse a tree level by level. 2. Output requires levels in reverse order. 3. BFS or DFS with level tracking is applicable. 4. Problem involves grouping nodes by depth.

Signature Phrases

bottom-up level order traversallevel by level from leaf to rootreverse the level order

NOT This Pattern When

Inorder, preorder, or postorder traversals are different patterns focusing on node visit order, not levels.

Similar Problems

Binary Tree Level Order Traversal - similar but top-down orderZigzag Level Order Traversal - level order with alternating directionsN-ary Tree Level Order Traversal - generalization to 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. What is the time and space complexity of the optimal DFS approach for the binary tree right side view problem, where the tree has n nodes and height h?

medium

A. Time: O(n), Space: O(h)

B. Time: O(h), Space: O(h)

C. Time: O(n), Space: O(n)

D. Time: O(n log n), Space: O(n)

Solution

1. Step 1: Identify time complexity

   The DFS visits each node exactly once, so time complexity is O(n).

2. Step 2: Identify space complexity

   Space is dominated by recursion stack, which is at most the height h of the tree, so O(h).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   DFS recursion stack space depends on tree height, not total nodes [OK]

Hint: DFS time O(n), space O(tree height) [OK]

Common Mistakes:

• Assuming space is O(n) due to storing output or recursion stack
• Confusing time complexity with BFS level order traversal
• Thinking recursion stack is O(n log n) due to tree balancing

3. What is the time complexity of the BFS level order traversal approach used to determine if two nodes in a binary tree are cousins, assuming the tree has n nodes?

medium

A. O(n^2) because each level is processed separately

B. O(n log n) due to repeated queue operations

C. O(n) because each node is visited exactly once

D. O(h) where h is the height of the tree due to level traversal

Solution

1. Step 1: Identify BFS traversal cost

   BFS visits each node once, enqueuing and dequeuing each node exactly one time.

2. Step 2: Analyze per-node operations

   Each node's children are checked once, so total operations scale linearly with n.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Linear traversal over all nodes confirms O(n) time [OK]

Hint: BFS visits each node once, so O(n) time [OK]

Common Mistakes:

• Confusing BFS with DFS recursion stack cost
• Assuming repeated level processing causes O(n^2)
• Mistaking height for total nodes

4. What is the time complexity of the BFS-based solution for finding the largest value in each tree row, assuming n is the number of nodes and w is the maximum width of the tree?

medium

A. O(n * w) because for each node we scan all nodes at its level

B. O(n log w) due to maintaining a max heap per level

C. O(n) because each node is enqueued and dequeued exactly once

D. O(w) since we only track the maximum per level

Solution

1. Step 1: Identify that each node is processed once

   Each node is enqueued once and dequeued once, so total operations proportional to n.

2. Step 2: Confirm no nested loops over nodes beyond level size

   Inner loop runs for each level's nodes, summing to n overall, so total time is O(n).

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Each node visited once -> O(n) time [OK]

Hint: Each node processed once in BFS -> O(n) time [OK]

Common Mistakes:

• Confusing level width w as multiplicative factor
• Assuming sorting or heap operations per level
• Ignoring that inner loop sums to n over all levels

5. What is the time complexity of the optimal iterative BFS approach using two queues for N-ary tree level order traversal, where n is the number of nodes in the tree?

medium

A. O(n) because each node is visited exactly once

B. O(n²) because each node's children are enqueued multiple times

C. O(n log n) due to sorting nodes at each level

D. O(n + m) where m is the maximum number of children per node

Solution

1. Step 1: Identify operations per node

   Each node is enqueued and dequeued exactly once, and its children are iterated once.

2. Step 2: Sum over all nodes

   Since total nodes are n, total operations scale linearly with n.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Traversal visits each node once -> O(n) time [OK]

Hint: BFS visits each node once, no repeated work [OK]

Common Mistakes:

• Assuming children are enqueued multiple times causing O(n²)