Level order traversal

Easy

Problem

Return the tree's node values level by level, from top to bottom and left to right within each level, as a list of levels.

Example 1

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

Test cases

Case 1

Input:    [3,9,20,null,null,15,7]
Expected: [[3],[9,20],[15,7]]

Case 2

Input:    [1]
Expected: [[1]]

Case 3

Input:    []
Expected: []

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution1 approach

1. BFS with a queue

Time O(n)Space O(width)

Process the tree one level at a time; the queue length at the start of each round is the level size.

function levelOrder(root) {
if (!root) return [];
const res = [], q = [root];
while (q.length) {
const level = [];
for (let k = q.length; k > 0; k--) {
const node = q.shift();
level.push(node.val);
if (node.left) q.push(node.left);
if (node.right) q.push(node.right);
}
res.push(level);
}
return res;
}