Binary Tree Level Order Traversal — Problem & Solution
Binary Tree Level Order Traversal solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Binary Tree Level Order Traversal is a medium coding problem on breadth-first search and trees, asked in Amazon, Microsoft, Meta and Bloomberg interviews.
- Difficulty: Medium
- Topics: Breadth-First Search, Trees
- Asked at: Amazon, Microsoft, Meta, Bloomberg
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given the root of a binary tree, return its node values level by level: one list per level, from the root's level down, each list reading its level from left to right.
Example 1
Input: root = [3,9,20,null,null,15,7]
Output: [[3],[9,20],[15,7]]
Explanation: Level 1 holds 3, level 2 holds 9 and 20, level 3 holds 15 and 7.
Example 2
Input: root = [1]
Output: [[1]]
Explanation: A single node is a single level.
Example 3
Input: root = []
Output: []
Explanation: An empty tree has no levels.
Constraints
0 <= number of nodes <= 2000-1000 <= Node.val <= 1000
Hints for Binary Tree Level Order Traversal
Hint 1
A queue hands nodes back in the order they were added — add children left before right and the nodes come out level after level.
Hint 2
The difficulty is knowing where one level ends and the next begins.
Hint 3
At the start of each level the queue holds exactly that level: read its size first, then take exactly that many nodes into one list.
How to solve Binary Tree Level Order Traversal
Breadth-first search with a queue visits nodes in level order; fixing the queue's size at the start of each round separates the levels.
Approach
- If the tree is empty, return an empty list.
- Put the root in a queue.
- While the queue is not empty: let
sizebe its length, takesizenodes from the front, append their values to a new list and push each one's left then right child. - Append that list to the answer and repeat.
Why it works
By induction, when a round starts the queue holds exactly the nodes of one level in left-to-right order: the round removes all of them and adds exactly their children, in left-to-right order, which is the next level.
Complexity
- Time —
O(n) - Space —
O(w), w the largest number of nodes on one level (plus the output)
Pitfalls
- Read the queue's size before the inner loop — it grows while children are added.
- Return
[], not[[]], for an empty tree.
Reference solution
Python
from typing import List, Optional
def levelOrder(root: Optional[TreeNode]) -> List[List[int]]:
out = []
level = [root] if root else []
while level:
out.append([node.val for node in level])
nxt = []
for node in level:
if node.left:
nxt.append(node.left)
if node.right:
nxt.append(node.right)
level = nxt
return outJava
public static int[][] levelOrder(TreeNode root) {
List<int[]> out = new ArrayList<>();
Deque<TreeNode> queue = new ArrayDeque<>();
if (root != null) queue.add(root);
while (!queue.isEmpty()) {
int size = queue.size();
int[] row = new int[size];
for (int i = 0; i < size; i++) {
TreeNode node = queue.poll();
row[i] = node.val;
if (node.left != null) queue.add(node.left);
if (node.right != null) queue.add(node.right);
}
out.add(row);
}
return out.toArray(new int[0][]);
}C++
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> out;
queue<TreeNode*> q;
if (root) q.push(root);
while (!q.empty()) {
int size = (int) q.size();
vector<int> row;
for (int i = 0; i < size; i++) {
TreeNode* node = q.front();
q.pop();
row.push_back(node->val);
if (node->left) q.push(node->left);
if (node->right) q.push(node->right);
}
out.push_back(row);
}
return out;
}JavaScript
var levelOrder = function(root) {
var out = [];
if (root === null) return out;
var queue = [root], head = 0;
while (head < queue.length) {
var end = queue.length, row = [];
while (head < end) {
var node = queue[head++];
row.push(node.val);
if (node.left !== null) queue.push(node.left);
if (node.right !== null) queue.push(node.right);
}
out.push(row);
}
return out;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 156 breadth-first search problems · the whole catalogue
Learn the technique: Breadth-First Search (BFS) · Binary Trees and Tree Traversals