Editorial: Binary Tree Level Order Traversal

1 Intuition

BFS naturally processes nodes level by level using a queue. Add nodes to queue, process each level, and collect results. This gives us the level-order traversal.

2 Approach

1. Initialize queue with root node 2. Initialize result list 3. While queue not empty: - Get current level size - Process all nodes at current level - Add level's values to result - Add their children to queue for next level 4. Return result

3 Complexity Analysis

**Time Complexity:** O(n) - visit each node once **Space Complexity:** O(w) - w is max width of tree Max queue size is the widest level of tree.

4 Solution Code

from collections import deque
def levelOrder(root):
    if not root:
        return []
    result = []
    queue = deque([root])
    while queue:
        level_size = len(queue)
        level = []
        for _ in range(level_size):
            node = queue.popleft()
            level.append(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        result.append(level)
    return result

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

5 Code Walkthrough

For root = [3,9,20,null,null,15,7]: - Queue: [3], Result: [] - Process 3: Add 9,20 to queue, Result: [[3]] - Process 9,20: Add 15,7 to queue, Result: [[3],[9,20]] - Process 15,7: Result: [[3],[9,20],[15,7]] Done