Binary Tree Level Order Traversal
Last Updated: March 29, 2026
Understanding the Problem
We have a binary tree, and we need to return its values grouped by level. All nodes at the same depth go into the same sublist, and within each sublist, nodes appear left to right. The result is a list of lists, where the first sublist contains just the root, the second contains all nodes at depth 1, and so on.
This is different from standard tree traversals (inorder, preorder, postorder) because those follow branch paths. Here, we need to process nodes "horizontally" across the tree. The core challenge is: how do we visit every node at depth d before visiting any node at depth d+1?
That question points directly toward BFS. But as we'll see, DFS can also solve this if we track the depth of each node.
Key Constraints:
Number of nodes in range [0, 2000]— With at most 2,000 nodes, even an O(n^2) approach would be fine performance-wise. But the natural solutions here are all O(n), so efficiency isn't the challenge. The real question is choosing the right traversal strategy.-1000 <= Node.val <= 1000— Node values can be negative. This doesn't affect the traversal logic, but make sure your solution doesn't assume positive values.- The tree can be empty (0 nodes), so we need to handle the null root case.
Approach 1: DFS with Level Tracking
Intuition
Your first instinct might be DFS since it's a tree problem, and DFS is the default tool for trees. DFS doesn't naturally process nodes level by level, but we can work around that. The trick is to carry the current depth as a parameter. Every time we visit a node, we know its level, so we can put its value into the right bucket.
Picture it this way: DFS dives deep first, but if we tag each node with its depth, we can sort the results into levels after the fact. We use a list of lists, where index 0 holds level 0's values, index 1 holds level 1's values, and so on. When we visit a node at depth d, we append its value to result[d].
The one subtlety is ordering within each level. We need left-to-right order. Since DFS visits the left subtree before the right subtree (assuming we recurse left first), and we append values as we encounter them, the left-to-right order is preserved automatically.
Algorithm
- If the root is null, return an empty list.
- Create an empty list of lists called
result. - Define a recursive helper function
dfs(node, level): - If
nodeis null, return. - If
levelequals the current size ofresult, append a new empty list (we've reached a new level for the first time). - Append
node.valtoresult[level]. - Recurse on the left child with
level + 1. - Recurse on the right child with
level + 1. - Call
dfs(root, 0)and returnresult.
Example Walkthrough
Code
- Time Complexity: O(n). We visit each node exactly once. At each node, we do O(1) work (check the list size, append a value). So the total time is O(n) where n is the number of nodes.
- Space Complexity: O(n). The result list holds all n node values. The recursion stack can go as deep as the height of the tree, which is O(n) in the worst case (skewed tree) and O(log n) for a balanced tree.
The DFS approach works correctly but processes nodes "vertically" down branches rather than "horizontally" across levels. Is there an approach where the traversal itself naturally produces the level-by-level order?
Approach 2: BFS with Queue (Optimal)
Intuition
BFS is the textbook answer here, and for good reason. BFS uses a queue, and a queue's FIFO (first-in, first-out) property is exactly what we need. When we process a node and enqueue its children, those children go to the back of the queue. All nodes at the current level get processed before any of their children. That's level order traversal by definition.
The one piece we need to add is level separation. Plain BFS gives us nodes in the right order but doesn't tell us where one level ends and the next begins. The classic trick: at the start of each level, check the queue's current size. That size tells you exactly how many nodes belong to the current level. Process that many nodes, and everything you enqueue during that process belongs to the next level.
The key insight is that a queue naturally maintains the discovery order. When we start with just the root, the queue has one node. We dequeue it and enqueue its children. Now the queue holds all level-1 nodes. We dequeue all of them (we know how many because we checked the queue size) and enqueue their children. Now the queue holds all level-2 nodes. This pattern repeats until the queue is empty.
The levelSize variable is what makes level separation possible. Without it, we'd get all nodes in the correct BFS order but couldn't tell where one level ends and another begins. By snapshotting the queue size at the start of each iteration, we know exactly how many nodes to process before moving to the next level.
Algorithm
- If the root is null, return an empty list.
- Create a queue and add the root to it.
- While the queue is not empty:
- Record the current queue size as
levelSize(the number of nodes in this level). - Create an empty list for the current level.
- Process exactly
levelSizenodes from the queue: - Dequeue a node, add its value to the current level's list.
- If the node has a left child, enqueue it.
- If the node has a right child, enqueue it.
- Add the current level's list to the result.
- Return the result.
Example Walkthrough
Code
- Time Complexity: O(n). Every node is enqueued once and dequeued once. Each enqueue/dequeue is O(1). So the total time is O(n).
- Space Complexity: O(n). The result list stores all n values. The queue holds at most one level's worth of nodes at a time. In the worst case (a complete binary tree), the last level has about n/2 nodes, so the queue is O(n).