Binary Tree Level Order Traversal
The key idea
Process the tree one full level at a time using a queue. Before each round, record how many nodes are currently in the queue: that count is exactly the size of the current level, so you can pop precisely that many nodes into one group before moving on.
Problem
Given the root of a binary tree, return the level order traversal of its nodes' values. A level order traversal visits the nodes level by level, from top to bottom, and within each level it reads them from left to right. The result groups the values of each level into its own list, so the outer list holds one inner list per level, ordered from the root level downward.
Constraints
- The number of nodes in the tree is in the range
[0, 2000]. -1000 <= Node.val <= 1000
Examples
Input: root = [3,9,20,null,null,15,7]
Output: [[3],[9,20],[15,7]]
Input: root = [1]
Output: [[1]]
Input: root = []
Output: []
Complexity
Time: O(n) Space: O(n)
See the full solution
- ✓Full worked approach
- ✓Reference code in 5 languages
- ✓Problem-solving tips
- ✓Step-by-step animated visualization
More BFS / DFS problems
- 01 MatrixMEDIUM
- Average of Levels in Binary TreeEASY
- Binary Tree Level Order Traversal IIMEDIUM
- Binary Tree Right Side ViewMEDIUM
- Binary Tree Zigzag Level Order TraversalMEDIUM
- Find Bottom Left Tree ValueMEDIUM
- Find Largest Value in Each Tree RowMEDIUM
- Flood FillEASY
- Keys and RoomsMEDIUM
- Max Area of IslandMEDIUM
- Maximum Level Sum of a Binary TreeMEDIUM
- Minimum Depth of Binary TreeEASY