Binary Tree Level Order Traversal

medium Trees

Given the root of a binary tree, return its level order traversal as a list of lists, where each inner list contains the values of nodes at that depth level, ordered from left to right. The tree can have between 0 and 2000 nodes with values in the range [-1000, 1000].

Example

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

Level 0 has just the root 3. Level 1 has 9 and 20 (left to right). Level 2 has 15 and 7.

Use BFS with a queue. At each step, record how many nodes are in the queue (that's the current level's size), then process exactly that many nodes — collecting their values and adding their children for the next level. This naturally groups nodes by depth.

Why this works

BFS naturally visits nodes level by level. The key trick is snapshotting the queue size at the start of each level — that tells you exactly how many nodes belong to the current depth. You process that many nodes, and any children you add during this pass belong to the next level.

Step by step

Seed the queue — start with the root node in a queue.
Snapshot the level size — record len(queue) before processing; this is how many nodes are at the current depth.
Process the level — dequeue exactly that many nodes, collect their values, and enqueue their children.
Repeat — continue until the queue is empty; each iteration produces one level’s list.

Time: O(n) Space: O(n)

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


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 size = queue.size(); // snapshot level size before adding children
            List<Integer> level = new ArrayList<>();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                level.add(node.val);
                if (node.left != null) {
                    queue.offer(node.left); // enqueue children for next level
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
            result.add(level);
        }
        return result;
    }
}

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


class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> result;
        if (!root) {
            return result;
        }
        queue<TreeNode*> q;
        q.push(root);
        while (!q.empty()) {
            int size = q.size(); // snapshot level size before adding children
            vector<int> level;
            for (int i = 0; i < size; i++) {
                TreeNode* node = q.front();
                q.pop();
                level.push_back(node->val);
                if (node->left) {
                    q.push(node->left); // enqueue children for next level
                }
                if (node->right) {
                    q.push(node->right);
                }
            }
            result.push_back(level);
        }
        return result;
    }
};

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


from collections import deque

def levelOrder(root: TreeNode | None) -> list[list[int]]:
    if not root:
        return []
    result = []
    queue = deque([root])
    while queue:
        level = []
        for _ in range(len(queue)):  # process exactly this level's nodes
            node = queue.popleft()
            level.append(node.val)
            if node.left:
                queue.append(node.left)  # enqueue children for next level
            if node.right:
                queue.append(node.right)
        result.append(level)
    return result