Binary Tree Level Order Traversal — Practice

Problem

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

Examples

Example 1

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

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

Constraints

•The number of nodes in the tree is in the range [0, 2000].

Hints

Hint 1

BFS with a queue. At each level, record queue size to know when the level ends.

Hint 2

A DFS-based alternative also works: track each node's DEPTH as you recurse, and append its value to result[depth] — you don't strictly need a queue for level-order output.

Solutions

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(); // snapshot size before processing
        List<Integer> 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;
}

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