Binary Tree Level Order Traversal solution and explanation
Google
9 more videos on this problem
Binary Tree Level Order Traversal - BFS - Leetcode 102NeetCode · 9:36 · 286K views
Binary Tree Level Order Traversal | Live Coding with Explanation | Leetcode - 102Algorithms Made Easy · 11:34 · 16K views
Binary Tree Level Order Traversal (BFS) - Leetcode 102 - Trees (Python)Greg Hogg · 9:49 · 14K views
LeetCode 102. Binary Tree Level Order Traversal - Interview Prep Ep 70Fisher Coder · 8:58 · 7K views
BINARY TREE LEVEL ORDER TRAVERSAL | PYTHON SOLUTION | LEETCODE # 102Cracking FAANG · 12:03 · 3K views
Binary Tree Level Order Traversal - LeetCode 102 - JavaScriptAlgoJS · 5:06 · 2K views
Binary Tree Level Order Traversal - LeetCode 102 - LeetCode SolutionsOne Code Man · 3:52 · 2K views
102. Binary Tree Level Order Traversal Java SolutionCode with Carter · 8:54 · 1K views
Binary Tree Level Order | LeetCode 102 (Medium)Destination FAANG · 12:14 · 709 views
LeetCode Problem 102: Binary Tree Level Order Traversal in Java - FAANG Coding Interview - Blind 75KeyStrokes · 11:52 · 693 views
The problem
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).
Example 1:
Input: root = [3,9,20,null,null,15,7] Output: [[3],[9,20],[15,7]]
Example 2:
Input: root = [1] Output: [[1]]
Example 3:
Input: root = [] Output: []
Constraints:
- The number of nodes in the tree is in the range
[0, 2000]. -1000 <= Node.val <= 1000
Approach overview
Problem Overview: Given the root of a binary tree, return the node values level by level from left to right. Each level should appear as a separate list in the final result.
Approach 1: Breadth-First Search Using Queue (O(n) time, O(w) space)
This problem naturally fits Breadth-First Search. Use a queue to process nodes level by level. Start by pushing the root node into the queue. For each iteration, record the current queue size because it represents the number of nodes at that level. Dequeue exactly that many nodes, append their values to the current level list, and push their left and right children into the queue. Continue until the queue is empty. Every node is visited exactly once, so the time complexity is O(n). The queue can hold up to the width of the tree, giving O(w) auxiliary space in the worst case.
This approach mirrors the conceptual definition of level order traversal. Because nodes are processed in the same order they appear by depth, the implementation stays simple and predictable. When working with tree traversal problems that require grouping nodes by depth, BFS is usually the first algorithm to consider.
Approach 2: Depth-First Search with Precomputed Levels (O(n) time, O(h) space)
A binary tree can also be traversed using DFS while tracking the current depth. During recursion, pass the level index as a parameter. If the result list does not yet contain a list for that depth, create one. Then append the current node's value to result[level]. Recursively process the left child and then the right child with level + 1.
This method still visits each node exactly once, so the runtime remains O(n). The recursion stack grows to the tree height h, giving O(h) auxiliary space (excluding the output). DFS is useful when the problem already requires recursive traversal or when you want tighter control over recursion logic. The tradeoff is that level grouping must be handled manually using the depth index.
Recommended for interviews: The BFS queue approach is what interviewers usually expect first. Level order traversal is essentially BFS applied to a tree, so recognizing that mapping quickly demonstrates algorithmic intuition. Showing the DFS-with-level-index variant afterward demonstrates deeper understanding of tree traversal patterns and flexibility in implementation.
Approach 1: Breadth-First Search Using Queue
This approach utilizes a queue to perform a Breadth-First Search (BFS) on the binary tree. Starting from the root, traverse each level of the tree and store values of nodes in separate lists for each level. By using a queue, we can efficiently keep track of nodes at the current level and their respective children for the next level.
from collections import deque
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def levelOrder(root):
if not root:
return []
result = []
queue = deque([root])
while queue:
level_size = len(queue)
level_nodes = []
for _ in range(level_size):
node = queue.popleft()
level_nodes.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
result.append(level_nodes)
return resultimport java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode() {}
TreeNode(int val) { this.val = val; }
TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
}
public class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> levels = new ArrayList<>();
if (root == null) return levels;
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
int levelSize = queue.size();
List<Integer> level = new ArrayList<>();
for (int i = 0; i < levelSize; i++) {
TreeNode node = queue.poll();
level.add(node.val);
if (node.left != null) queue.add(node.left);
if (node.right != null) queue.add(node.right);
}
levels.add(level);
}
return levels;
}
}function TreeNode(val, left, right) {
this.val = (val===undefined ? 0 : val);
this.left = (left===undefined ? null : left);
this.right = (right===undefined ? null : right);
}
function levelOrder(root) {
if (!root) return [];
const result = [];
const queue = [root];
while (queue.length > 0) {
const levelSize = queue.length;
const levelNodes = [];
for (let i = 0; i < levelSize; i++) {
const node = queue.shift();
levelNodes.push(node.val);
if (node.left) queue.push(node.left);
if (node.right) queue.push(node.right);
}
result.push(levelNodes);
}
return result;
}We use a deque from the collections module to easily append and pop nodes from the queue. Starting with the root node if it is not null, we add it to the queue. For each level, determine the number of nodes at that level (i.e., the size of the queue), then iterate over them, adding each node's children to the queue for the next level. Collect and return the node values in a nested list representing each level.
Time Complexity: O(n), where n is the number of nodes in the tree because each node is visited once.
Space Complexity: O(n), as we store all nodes at each level in the queue.
Approach 2: Depth-First Search (DFS) with Precomputed Levels
This approach involves using a Depth-First Search (DFS) where we pass along the current level during the recursive calls. By keeping track of the current depth, we can directly add node values to their appropriate level in our result list, creating new levels in our result list as needed.
#include <vector>
using namespace std;
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode() : val(0), left(nullptr), right(nullptr) {}
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
void dfs(TreeNode* node, int level, vector<vector<int>>& levels) {
if (!node) return;
if (level == levels.size())
levels.push_back(vector<int>());
levels[level].push_back(node->val);
dfs(node->left, level + 1, levels);
dfs(node->right, level + 1, levels);
}
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> levels;
dfs(root, 0, levels);
return levels;
}#include <stdio.h>
#include <stdlib.h>
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
};
void dfs(struct TreeNode* node, int level, int** result, int* returnSize, int** resultColSizes) {
if (!node) return;
if (level >= *returnSize) {
*returnSize += 1;
result[*returnSize - 1] = (int*)malloc(2000 * sizeof(int));
(*resultColSizes)[*returnSize - 1] = 0;
}
result[level][(*resultColSizes)[level]] = node->val;
(*resultColSizes)[level] += 1;
dfs(node->left, level + 1, result, returnSize, resultColSizes);
dfs(node->right, level + 1, result, returnSize, resultColSizes);
}
int** levelOrder(struct TreeNode* root, int* returnSize, int** resultColSizes) {
*returnSize = 0;
int** result = (int**)malloc(2000 * sizeof(int*));
*resultColSizes = (int*)malloc(2000 * sizeof(int));
dfs(root, 0, result, returnSize, resultColSizes);
return result;
}using System;
using System.Collections.Generic;
public class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int x) { val = x; }
}
public class Solution {
public IList<IList<int>> LevelOrder(TreeNode root) {
var levels = new List<IList<int>>();
DFS(root, 0, levels);
return levels;
}
private void DFS(TreeNode node, int level, List<IList<int>> levels) {
if (node == null) return;
if (level == levels.Count)
levels.Add(new List<int>());
levels[level].Add(node.val);
DFS(node.left, level + 1, levels);
DFS(node.right, level + 1, levels);
}
}Invoke the DFS function recursively by starting at the root node. We use a vector of vectors to represent levels during traversal. For each visited node, determine the current level size and append values to their respective level container, expanding the container list when necessary. Recurse into children while maintaining depth count to achieve the level order.
Time Complexity: O(n), where n is the total number of nodes.
Space Complexity: O(h) on the call stack, plus O(n) for storing the result, where h is the height of the tree.
Approach 3: BFS
We can use the BFS method to solve this problem. First, enqueue the root node, then continuously perform the following operations until the queue is empty:
- Traverse all nodes in the current queue, store their values in a temporary array
t, and then enqueue their child nodes. - Store the temporary array
tin the answer array.
Finally, return the answer array.
The time complexity is O(n), and the space complexity is O(n). Here, n is the number of nodes in the binary tree.
/**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
function levelOrder(root: TreeNode | null): number[][] {
const ans: number[][] = [];
if (!root) {
return ans;
}
const q: TreeNode[] = [root];
while (q.length) {
const t: number[] = [];
const qq: TreeNode[] = [];
for (const { val, left, right } of q) {
t.push(val);
left && qq.push(left);
right && qq.push(right);
}
ans.push(t);
q.splice(0, q.length, ...qq);
}
return ans;
}/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func levelOrder(root *TreeNode) (ans [][]int) {
if root == nil {
return
}
q := []*TreeNode{root}
for len(q) > 0 {
t := []int{}
for n := len(q); n > 0; n-- {
node := q[0]
q = q[1:]
t = append(t, node.Val)
if node.Left != nil {
q = append(q, node.Left)
}
if node.Right != nil {
q = append(q, node.Right)
}
}
ans = append(ans, t)
}
return
}// Definition for a binary tree node.
// #[derive(Debug, PartialEq, Eq)]
// pub struct TreeNode {
// pub val: i32,
// pub left: Option<Rc<RefCell<TreeNode>>>,
// pub right: Option<Rc<RefCell<TreeNode>>>,
// }
//
// impl TreeNode {
// #[inline]
// pub fn new(val: i32) -> Self {
// TreeNode {
// val,
// left: None,
// right: None
// }
// }
// }
use std::cell::RefCell;
use std::collections::VecDeque;
use std::rc::Rc;
impl Solution {
pub fn level_order(root: Option<Rc<RefCell<TreeNode>>>) -> Vec<Vec<i32>> {
let mut ans = Vec::new();
if let Some(root_node) = root {
let mut q = VecDeque::new();
q.push_back(root_node);
while !q.is_empty() {
let mut t = Vec::new();
for _ in 0..q.len() {
if let Some(node) = q.pop_front() {
let node_ref = node.borrow();
t.push(node_ref.val);
if let Some(ref left) = node_ref.left {
q.push_back(Rc::clone(left));
}
if let Some(ref right) = node_ref.right {
q.push_back(Rc::clone(right));
}
}
}
ans.push(t);
}
}
ans
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Breadth-First Search Using Queue | Time Complexity: O(n), where n is the number of nodes in the tree because each node is visited once. |
| Depth-First Search (DFS) with Precomputed Levels | Time Complexity: O(n), where n is the total number of nodes. |
| BFS | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Breadth-First Search Using Queue | O(n) | O(w) | Standard level order traversal; easiest and most intuitive solution |
| Depth-First Search with Level Index | O(n) | O(h) | Useful when implementing recursive tree traversals or when DFS structure is preferred |
Frequently asked questions
Is Binary Tree Level Order Traversal easy or hard?
Binary Tree Level Order Traversal is generally considered a medium-level problem. The core logic is straightforward BFS, but candidates must correctly manage level boundaries and queue operations during traversal.
Binary Tree Level Order Traversal Python/Java solution
In Python, collections.deque is typically used to implement the BFS queue efficiently. In Java, developers commonly use LinkedList or ArrayDeque as the queue implementation while processing nodes level by level.
How to solve Binary Tree Level Order Traversal in O(n)?
Use a queue to perform a breadth-first traversal. Push the root into the queue, process nodes level by level by iterating through the current queue size, and enqueue left and right children. Since each node is processed once, the overall complexity is O(n).
What is the best approach for Binary Tree Level Order Traversal?
Breadth-First Search (BFS) using a queue is the most common approach. Nodes are processed level by level by pushing children into a queue while iterating through the current level size. This guarantees each node is visited once with O(n) time complexity.
Is Binary Tree Level Order Traversal asked at Google/Amazon/Meta?
Binary tree traversal problems, including level order traversal, appear frequently in interviews at companies like Google, Amazon, and Meta. They test understanding of BFS, queue usage, and basic tree data structure operations.
What data structure is used in Binary Tree Level Order Traversal?
A queue is the primary data structure used for the BFS approach. It maintains the processing order of nodes so that nodes at the same depth are visited together before moving to the next level.
What is the time complexity of Binary Tree Level Order Traversal?
The time complexity is O(n) because each node in the binary tree is visited exactly once. The auxiliary space is O(w) for BFS where w is the maximum width of the tree, or O(h) for a DFS recursion stack where h is the tree height.