Binary Tree Level Order Traversal Without a Queue: The Recursive Trick
Solve binary tree level order traversal with DFS recursion and a level parameter — no queue needed. Intuition, JavaScript code, a worked trace, and complexity.
This article has an interactive companion
Don't just read it — step through it interactively, one state change at a time.
Level order traversal is the poster child for BFS: push the root into a queue, pop a node, enqueue its children, repeat. So it feels almost like a trick question when an interviewer asks you to do it recursively — recursion is depth-first, and level order is breadth-first. They pull in opposite directions.
The resolution is one small idea: carry the depth down as a parameter. Once every recursive call knows which level it's on, you can drop each value into a bucket indexed by that level — and the grouping comes out right no matter what order DFS actually visits the nodes.
That single reframe turns a queue-based algorithm into six lines of recursion, and it's the same "index by a computed key" move that powers a surprising number of tree problems.
The problem
Given the root of a binary tree, return its node values grouped by level, top to bottom, left to right. Level 0 is the root, level 1 is its children, and so on. The output is an array of arrays — one sub-array per depth.
Input: 3
/ \
9 20
/ \
15 7
Output: [[3], [9, 20], [15, 7]]Read as level-order input that's [3, 9, 20, null, null, 15, 7]. Node 3 sits alone at level 0, 9 and 20 share level 1, and 15 and 7 share level 2. The answer preserves both the level grouping and left-to-right order inside each level.
The brute force baseline
The textbook answer is BFS with a queue. Process the tree one level at a time: record how many nodes are on the current level, dequeue exactly that many, collect their values, and enqueue their children for the next round.
function levelOrder(root) {
if (!root) return [];
const ans = [];
const queue = [root];
while (queue.length > 0) {
const levelSize = queue.length;
const level = [];
for (let i = 0; i < levelSize; i++) {
const node = queue.shift();
level.push(node.val);
if (node.left) queue.push(node.left);
if (node.right) queue.push(node.right);
}
ans.push(level);
}
return ans;
}Nothing is wrong with this — it's O(n) time and the intended solution for the iterative version. But it isn't slow so much as it's a different shape of answer than "do it recursively." Two things make it heavier than it needs to be: it allocates and manages an explicit queue, and queue.shift() on a plain array is O(n) because it re-indexes every remaining element (a real queue or a head pointer fixes that, but now you're bookkeeping). The recursive version needs neither.
The key insight: let the level be the index
Stop thinking about when a node is visited and think about where its value belongs. A node at depth level always belongs in ans[level]. That's true regardless of whether DFS reaches it before or after its cousins on the same level.
So carry the depth down through the recursion. Every call receives its level, and the value gets pushed into ans[level]:
ans[level].push(node.val)Because you always recurse left before right, values land in each bucket in left-to-right order automatically. The first time you reach a brand-new depth, that bucket doesn't exist yet — so create it lazily right before the first push. The level parameter is the entire mechanism; it replaces the queue with an array index.
The optimal solution
This is the exact algorithm the visualizer steps through — a preorder DFS that grows ans on demand and uses level as the bucket index.
var levelOrder = function (root) {
if (!root) return [];
let ans = [];
function traversal(curr, level) {
if (!ans[level]) ans[level] = [];
ans[level].push(curr.val);
curr.left && traversal(curr.left, level + 1);
curr.right && traversal(curr.right, level + 1);
}
traversal(root, 0);
return ans;
};Three lines do all the work. if (!ans[level]) ans[level] = [] lazily creates a level's bucket the first time any node reaches that depth. ans[level].push(curr.val) files the value under its depth. The two short-circuit calls — curr.left && traversal(curr.left, level + 1) — descend into each child with the depth bumped by one, and skip the call entirely when a child is null. No queue, no explicit null-node handling, no level-size counting.
Walkthrough
Tracing [3, 9, 20, null, null, 15, 7]. Watch how ans fills by level even though the visit order is depth-first (3, 9, 20, 15, 7):
| Step | Call | level | ans[level] exists? | Action | ans after |
|---|---|---|---|---|---|
| 1 | traversal(3, 0) | 0 | no → create ans[0] | push 3 | [[3]] |
| 2 | traversal(9, 1) | 1 | no → create ans[1] | push 9 | [[3], [9]] |
| 3 | (9 has no children) | — | — | return up to 3 | [[3], [9]] |
| 4 | traversal(20, 1) | 1 | yes | push 20 | [[3], [9, 20]] |
| 5 | traversal(15, 2) | 2 | no → create ans[2] | push 15 | [[3], [9, 20], [15]] |
| 6 | (15 has no children) | — | — | return up to 20 | [[3], [9, 20], [15]] |
| 7 | traversal(7, 2) | 2 | yes | push 7 | [[3], [9, 20], [15, 7]] |
Step 4 is the one that makes the pattern click. DFS descends all the way down 9 before it ever touches 20, yet when 20 finally pushes, ans[1] already holds [9] — so 20 lands right after it, in correct left-to-right order. The level index, not the visit timing, decides placement. The recursion returns to the root and ans is [[3], [9, 20], [15, 7]].
Complexity
| Metric | Big-O | Why |
|---|---|---|
| Time | O(n) | each of the n nodes is visited once; create-bucket, push, and two calls are O(1) each |
| Space (output) | O(n) | ans stores every value across its sub-arrays |
| Space (recursion) | O(h) | the call stack goes as deep as the tree's height h |
Time is O(n) — you touch every node exactly once and do constant work per node. The recursion stack adds O(h) auxiliary space, where h is the tree height: about O(log n) for a balanced tree, but O(n) for a degenerate one-node-per-level chain. The BFS version trades that stack for an O(w) queue, where w is the maximum level width. Same asymptotic class, different constant and different failure mode on skewed trees.
Common mistakes
- Forgetting to create the bucket before pushing.
ans[level].push(...)throws ifans[level]is undefined. Theif (!ans[level]) ans[level] = []guard must run first, every time. - Bumping the level on the wrong branch. Both children are one level deeper than the parent, so both calls use
level + 1. Passinglevelto one andlevel + 1to the other silently corrupts the grouping. - Recursing right before left. DFS order is what preserves left-to-right within a level. Swap the two calls and every even level comes out reversed.
- Using
ans.length === levelas the create check on a sparse tree. The visualizer'sif (!ans[level])is robust because levels are always reached in increasing order here; but if you ever visit a deeper level before a shallower one, a length check breaks — prefer the existence check. - Assuming recursion is always safe. A pathologically deep tree (tens of thousands of nodes in a single chain) can overflow the call stack. That's the one case where the iterative BFS version is genuinely safer.
Where this pattern shows up next
Passing state down through recursion — here it's the level, elsewhere it's a running sum or a path — is the reusable move. These tree traversals build the same recursion muscle:
- Binary Tree Preorder Traversal — the root-left-right recursion this solution is shaped like, minus the level bucketing.
- Binary Tree Inorder Traversal — left-root-right ordering, the classic recursive traversal.
- Binary Tree Preorder Traversal - Iterative — the same visit order rebuilt with an explicit stack instead of recursion.
- Binary Tree Inorder Traversal - Iterative — how to unwind the recursion into a manual stack.
You can also step through the recursive level order traversal interactively and watch the call stack grow while each level's bucket fills.
FAQ
How can a recursive DFS produce level order output?
By carrying the current depth as a parameter and using it as an array index. Each node pushes its value into ans[level], so even though the recursion visits nodes depth-first, every value ends up filed under its correct level. The traversal order stops mattering because placement is decided by the level argument, not by when a node is reached.
Is the recursive version faster than BFS with a queue?
They're both O(n) time, so neither is asymptotically faster. The recursive version avoids the overhead of an explicit queue and, in JavaScript, sidesteps the O(n) cost of Array.shift(). It trades that for O(h) call-stack space. For most balanced trees the recursive version is cleaner and just as fast; BFS wins only when the tree is deep enough to risk a stack overflow.
Why do both child calls use level + 1?
Because a node's left and right children are at the same depth — exactly one level below their parent. Left and right are horizontal siblings, not vertical steps, so descending to either one increases the depth by the same amount. Both share the same bucket, ans[level + 1], which is why left-before-right recursion keeps them ordered correctly within that level.
What is the space complexity of recursive level order traversal?
The output array is O(n) since it holds every node's value. On top of that, the recursion uses O(h) stack space, where h is the tree's height — roughly O(log n) for a balanced tree and O(n) for a completely skewed one. The iterative BFS alternative replaces the O(h) stack with an O(w) queue, where w is the widest level.
When should I prefer the iterative BFS version instead?
Reach for BFS when the tree can be extremely deep — a chain of tens of thousands of nodes — because deep recursion can blow the call stack, while an explicit queue lives on the heap. BFS also maps more naturally onto variants that need per-level bookkeeping mid-traversal, like right-side view or zigzag. For ordinary balanced trees, the recursive version is shorter and just as efficient.
Make it stick: run this one yourself
Don't just read it — step through it interactively, one state change at a time.