Binary Tree Level Order Traversal
MediumTrees
Given the root of a binary tree, return its values level by level: an array with one array per level, from the root down, each listing that level’s values from left to right. An empty tree gives [].
On this page a tree is written in level order, top to bottom and left to right, with null where a child is missing: [6, 3, 8, 1] is 6 with children 3 and 8, and 3 with a left child 1.
Examples
Input: root = [8, 4, 12, null, 6, 10] Output: [[8], [4, 12], [6, 10]]
6 is the right child of 4 and 10 the left child of 12, so the third level reads 6, 10.
Input: root = [4, null, 9, 2] Output: [[4], [9], [2]]
Each level holds one node, so each inner array has one value.
Constraints
- The tree has 0 to 2000 nodes.
-1000 ≤ node.val ≤ 1000
Stuck?
Hint 1
Visit the nodes breadth first with a queue: each node’s children join the back of the queue, so the levels come out in order.
Hint 2
Before you read a level, note how many nodes the queue holds right then. Take exactly that many: they are the level, and the children they add make up the next one.
The idea
A queue hands nodes back in the order they joined, so if each node adds its children as it leaves, the nodes come out level by level. The one thing to track is where a level ends: when a level starts, the queue holds exactly that level and nothing else.
Time O(n)Extra space O(n)
Try it again with the idea in mind, or go through the code one step at a time.
The code, step by step
Step 1 of 5
The queue starts with the root. An empty tree starts with an empty queue, skips the loop and gives [].
function levelOrder(root) { const levels = []; const queue = root ? [root] : []; while (queue.length) { const size = queue.length; const level = []; for (let i = 0; i < size; i++) { const node = queue.shift(); level.push(node.val); if (node.left) queue.push(node.left); if (node.right) queue.push(node.right); } levels.push(level); } return levels;}The trap
Using queue.length as the loop bound looks the same as saving the size, but the length changes inside the loop as nodes leave and their children join. Where nodes have two children, the loop pulls the next level into the current one; at a level of leaves, it stops before the level is done. A tree that is one long chain keeps the length at 1, so it passes.
function levelOrder(root) { const levels = []; const queue = root ? [root] : []; while (queue.length) { const level = []; // reads queue.length while shifting from it, so levels run together for (let i = 0; i < queue.length; i++) { const node = queue.shift(); level.push(node.val); if (node.left) queue.push(node.left); if (node.right) queue.push(node.right); } levels.push(level); } return levels;}