Binary Tree Level Order Traversal

Problem Statement

You’re a tree surveyor mapping a binary tree level by level, from top to bottom, left to right. Return a list of lists, each containing the node values at that level. This medium-level BFS adventure is a panoramic sweep—queue up and explore!

Example

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

Tree:

   3
  / \
 9  20
   /  \
  15   7

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

Input: root = [1]

Output: [[1]]

Input: root = []

Output: []

Code

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

from collections import deque
class Solution:
    def levelOrder(self, 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
            

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

Explanation

• BFS Insight: Queue processes nodes level by level, ensuring top-down order.
• Flow: For each level, dequeue all nodes, enqueue their children, repeat.
• Example Walkthrough: [3,9,20,null,null,15,7] → queue=[3], [9,20], [15,7] → [[3],[9,20],[15,7]].
• Key Detail: levelSize tracks nodes per level to separate results.
• Alternative: DFS with level tracking possible but less intuitive.

Note