On this page

Binary Tree Level Order Traversal

Given the root of a binary tree, return the level order traversal of its nodes' values, that is, level by level from left to right, as a list of lists.

Constraints:

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

Intuition

Every example below uses this tree:

1 1
2 / \
3 2 3
4 / \ \
5 4 5 6

The expected output here is [[1], [2, 3], [4, 5, 6]].

Preorder, inorder and postorder go deep first (DFS). Level order goes wide first (BFS): finish everything at depth 0, then depth 1, then depth 2. The tool for that is a queue, because the first node discovered at a level should be the first one processed, and its children line up behind the nodes already waiting.

Approach: BFS with a Queue

  1. If the tree is empty, return an empty list.
  2. Put the root in a queue.
  3. While the queue is not empty:
    • Let size be the current queue length. Those size nodes are exactly one level.
    • Pop size nodes one by one, adding each value to a level list, and push each node's left then right child into the queue.
    • Add level to the answer.

Snapshotting size before the inner loop is the key detail. Children pushed during the loop belong to the next level, so they must not be counted in this round.

Code

class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> ans;
if (root == nullptr) return ans;
queue<TreeNode*> q;
q.push(root);
while (!q.empty()) {
int size = q.size();
vector<int> level;
for (int i = 0; i < size; i++) {
TreeNode* node = q.front();
q.pop();
level.push_back(node->val);
if (node->left != nullptr) q.push(node->left);
if (node->right != nullptr) q.push(node->right);
}
ans.push_back(level);
}
return ans;
}
};

Complexity

Time: O(n)

Each node is pushed into the queue once and popped once.

Space: O(w)

The queue holds at most one full level, where w is the maximum width of the tree. That is up to about n over 2 nodes for a complete tree, so O(n) in the worst case.

How to Explain It in an Interview

How to Explain it in an Interview

The 30-Second Spoken Pitch
"Level order is breadth first, so I use a queue instead of recursion. I push the root, and then while the queue is not empty I take a snapshot of its current size, because exactly that many nodes belong to the current level. I pop that many nodes, record their values into a level list, and push their left and right children for the next round. Then I append the level list to the answer. Taking the size before the inner loop is the important part, otherwise children from the next level would leak into this one. Time is O of n since each node enters and leaves the queue once, and space is O of the maximum width of the tree."
Next TopicIterative Preorder Traversal