Level order traversal
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: []
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;}