| 13 | }; |
| 14 | |
| 15 | const bfs = (queue /* Space O(W) */, levels = []) => { |
| 16 | while (queue.length) { |
| 17 | // Time O(N) |
| 18 | const level = []; |
| 19 | |
| 20 | for (let i = queue.length - 1; 0 <= i; i--) { |
| 21 | const node = queue.shift(); // Time O(N) ... This can be O(1) if we use an actual queue data structure |
| 22 | |
| 23 | if (node.left) queue.push(node.left); |
| 24 | if (node.right) queue.push(node.right); |
| 25 | |
| 26 | level.push(node.val); |
| 27 | } |
| 28 | |
| 29 | levels.push(level.slice()); |
| 30 | } |
| 31 | |
| 32 | return levels; |
| 33 | }; |
| 34 | |
| 35 | /** |
| 36 | * https://leetcode.com/problems/binary-tree-level-order-traversal/ |