Given the root of a binary tree, return its values level by level. Each level is one list, read from left to right, and the levels go from top to bottom.
DSA Animator › DSA Revision › Tree › Binary Tree Level Order Traversal
Remember: level by level means BFS with a queue. Read the queue size first, and that many nodes make one level. The video solves Binary Tree Level Order Traversal (LeetCode 102, Medium) with the BFS pattern from the Tree topic, and you can replay every step in the interactive Binary Tree Level Order Traversal animation.
Given the root of a binary tree, return its values level by level. Each level is one list, read from left to right, and the levels go from top to bottom.
For this tree, the answer has three lists. First 1, then 2 and 3, then 4, 5 and 7.
A normal depth-first traversal goes branch by branch, not level by level. You could carry the depth along and group the values afterwards, but there's a more natural tool.
Use a queue, which hands nodes back in the order they arrived. Before each level, read the queue's size: that is exactly how many nodes the level has. Pop that many nodes, record their values, and push their children for the next level.
Start with the root, 1, in the queue. The queue holds 1 node, so level 0 is just 1, and we push its children, 2 and 3. Now the queue size is 2, so level 1 takes two nodes. Pop 2, record it, and push its children, 4 and 5. Pop 3, record it, and push its only child, 7. Level 1 is 2 and 3, and the queue now holds 4, 5 and 7. The size is 3, so level 2 pops all three, and none of them have children. The queue is empty, so we're done: 1, then 2 and 3, then 4, 5 and 7.
In code, if the root is null, return an empty list. Otherwise, put the root in a queue. While the queue isn't empty, read its size, which is the size of this level. Pop that many nodes, add each value to the level list, and push its left and right children. Then add the level to the result. Every node enters and leaves the queue once, so it's O of n time, and O of n space for the queue.
Remember: level by level means BFS with a queue. Read the queue size first, and that many nodes make one level.