DSA problem
Binary Tree Level Order Traversal
Given the root of a binary tree, return the level order traversal of its nodes' values — that is, an array of arrays where each inner array contains the values of all nodes on one level, ordered from left to right.
This problem is the canonical example of breadth-first search on a tree, and it underpins almost every other problem in this category. The technique is to maintain a queue of nodes belonging to the current frontier, then to repeatedly: (1) snapshot the queue size to know how many nodes are on the current level, (2) dequeue exactly that many nodes while recording their values, and (3) enqueue their non-null children to set up the next level.
A common pitfall is to forget step (1): if you simply loop while (!queue.isEmpty()) and read queue.size() inside the loop, the size will grow as children are added and you will lose the level boundary. Snapshotting the size up front locks the level in place.
The algorithm visits each node exactly once and performs O(1) work per visit aside from the result append. Time complexity is therefore O(n) where n is the number of nodes, and space complexity is O(w) for the queue plus O(n) for the output, where w is the maximum width of the tree.
Examples
root = [3,9,20,null,null,15,7][[3],[9,20],[15,7]]root = [1][[1]]root = [][]Constraints
- The number of nodes in the tree is in the range [0, 2000].
- -1000 <= Node.val <= 1000
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.