Log inSign up
mediumleetcodeNot Started

Binary Tree Level Order Traversal

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Trees
Solve on leetcode
Lesson

Problem Statement

Given the root of a binary tree, return the level order traversal of its nodes' values. (i.e., from left to right, level by level as a 2D array of integers).

Example 1 · Example 1: Standard Tree:

Input: root = [3, 9, 20, null, null, 15, 7]
Output: [[3], [9, 20], [15, 7]]
Explanation: Level 0: [3]. Level 1: [9, 20]. Level 2: [15, 7].

Example 2 · Example 2: Single Node:

Input: root = [1]
Output: [[1]]
Explanation: Level 0: [1].

Constraints:

  • The number of nodes in the tree is in the range [0, 2000].
  • -1000 <= Node.val <= 1000

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Master the level-size snapshot BFS pattern.
  • Manage 2D grouping of hierarchical node data.
  • Understand queue-based breadth-first traversal.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Traverse tree row by row or level by level.
  • Group node values by their depth.
  • Shortest path in unweighted trees.

Algorithmic Decision Tree:

  • If root == null, return [].
  • Initialize queue with root.
  • While queue is not empty: size = queue.size(), drain size nodes, collect values, push children.

Connected Patterns:

Binary Tree Zigzag Level Order TraversalBinary Tree Right Side ViewMaximum Depth of Binary Tree

1. DFS with Depth Index Tracking

Intuition

Call dfs(root, 0). If level == ans.size(), append a new empty level list. Append node.val to ans[level]. Recurse left and right with level + 1.

When to apply: When recursive solution is preferred over queue BFS.

Algorithm

  1. Step 1: If root == null, return [].
  2. Step 2: Define dfs(node, depth):
  3. - If depth == ans.size(), ans.push([]).
  4. - ans[depth].push(node.val).
  5. - If node.left: dfs(node.left, depth + 1).
  6. - If node.right: dfs(node.right, depth + 1).
  7. Step 3: Call dfs(root, 0) and return ans.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5using namespace std;
6
7class Solution {
8public:
9 void dfs(TreeNode* node, int depth, vector<vector<int>>& ans) {
10 if (!node) return;
11 if (depth == (int)ans.size()) ans.push_back({});
12 ans[depth].push_back(node->val);
13 dfs(node->left, depth + 1, ans);
14 dfs(node->right, depth + 1, ans);
15 }
16 vector<vector<int>> levelOrder(TreeNode* root) {
17 vector<vector<int>> ans;
18 dfs(root, 0, ans);
19 return ans;
20 }
21};
22
23int main() {
24 // Sample driver execution
25 cout << "Execution completed successfully." << endl;
26 return 0;
27}
28

Time & Space Complexity

  • Time complexity: O(n) — Visits each node once in O(n) time.
  • Space complexity: O(h) — Call stack takes O(h) space.

2. BFS with Null Sentinel Delimiter

Intuition

Push root and null into queue. When popping node: if not null, append val to current level and push children. If null, current level is complete; push null if queue not empty.

When to apply: Historical classic BFS method.

Algorithm

  1. Step 1: If root == null return [].
  2. Step 2: Push root and null into queue.
  3. Step 3: While queue size > 1:
  4. - Pop node.
  5. - If node == null: finish level, push null.
  6. - Else: record val, push non-null children.
  7. Step 4: Return ans.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5using namespace std;
6
7class Solution {
8public:
9 vector<vector<int>> levelOrder(TreeNode* root) {
10 vector<vector<int>> ans;
11 if (!root) return ans;
12 queue<TreeNode*> q;
13 q.push(root);
14 q.push(nullptr);
15 vector<int> level;
16 while (q.size() > 1) {
17 TreeNode* node = q.front();
18 q.pop();
19 if (!node) {
20 ans.push_back(level);
21 level.clear();
22 q.push(nullptr);
23 } else {
24 level.push_back(node->val);
25 if (node->left) q.push(node->left);
26 if (node->right) q.push(node->right);
27 }
28 }
29 ans.push_back(level);
30 return ans;
31 }
32};
33
34int main() {
35 // Sample driver execution
36 cout << "Execution completed successfully." << endl;
37 return 0;
38}
39

Time & Space Complexity

  • Time complexity: O(n) — Processes all nodes and sentinel markers in O(n) time.
  • Space complexity: O(w) — Queue holds maximum level width O(w).

3. Standard Queue BFS with Level-Size Snapshot

Intuition

Initialize queue with root. While queue is non-empty: get size = q.size(). Create an empty level list. Run an inner loop from 0 to size - 1: pop node, add value to level list, and enqueue non-null children. Add level list to ans.

When to apply: Modern optimal industry standard BFS implementation.

Algorithm

  1. Step 1: If root == null, return [].
  2. Step 2: Initialize queue q, push root.
  3. Step 3: While q is not empty:
  4. - levelSize = q.size(), level = [].
  5. - For i = 0 to levelSize - 1:
  6. * node = q.pop().
  7. * level.push(node.val).
  8. * If node.left != null: q.push(node.left).
  9. * If node.right != null: q.push(node.right).
  10. - ans.push(level).
  11. Step 4: Return ans.

Level Order Trace for root = [3, 9, 20]

2 of 2 questions left today
Step 1 / 2
Trace timeline50% explored
Current operationSTEP 1 OF 2
Level 0: Queue has [3] (size=1)
Visual state
Values and pointers at this exact step
tree
Root
3
L
9
R
20

Node order shown; add connections to display explicit tree edges.

curr: 3
Check / comparison
Process Level 0: [3]
Decision / next transition
Add [3] to result. Queue becomes [9, 20].
Why this step matters

Level 0: Queue has [3] (size=1). Dequeue 3, record [3]. Enqueue left child 9 and right child 20. Queue is now [9, 20]. Level 0 complete: [[3]].

Step 1 / 2
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5using namespace std;
6
7class Solution {
8public:
9 vector<vector<int>> levelOrder(TreeNode* root) {
10 vector<vector<int>> ans;
11 if (!root) return ans;
12 queue<TreeNode*> q;
13 q.push(root);
14 while (!q.empty()) {
15 int levelSize = q.size();
16 vector<int> level;
17 for (int i = 0; i < levelSize; ++i) {
18 TreeNode* node = q.front();
19 q.pop();
20 level.push_back(node->val);
21 if (node->left) q.push(node->left);
22 if (node->right) q.push(node->right);
23 }
24 ans.push_back(level);
25 }
26 return ans;
27 }
28};
29
30int main() {
31 // Sample driver execution
32 cout << "Execution completed successfully." << endl;
33 return 0;
34}
35

Time & Space Complexity

  • Time complexity: O(n) — Every node is enqueued and dequeued exactly once, giving O(n) total time.
  • Space complexity: O(w) — Queue holds at most the maximum width w of the tree, which is O(n/2) = O(w).

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.DFS with Depth IndexO(n)O(h)Depth-first traversal indexing into 2D array by depth.Recursion depth.
2.BFS with Null SentinelO(n)O(w)Queue with null markers separating levels.Extra sentinel checks.
3.BFS with Level-Size SnapshotOptimalO(n)O(w)Inner loop of size q.size() draining current row.None. This is optimal.

Common Pitfalls & Crucial Edge Cases

Crucial Edge Cases to Validate:

  • Empty tree: root = [] -> returns [].
  • Single node tree: root = [1] -> returns [[1]].
  • Unbalanced / skewed trees.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Emphasize the snapshot of queue.size() at the start of each level loop.
  2. Mention that maximum queue size corresponds to the maximum width of the tree, which is at most ceil(n/2) for full binary trees.
  3. Show how DFS with depth tracking can also achieve the same result.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why must levelSize = q.size() be computed before the inner loop rather than using i < q.size() directly?

Back to DSA Sheet