LogoKode$word

LeetCode 102: Binary Tree Level Order Traversal – Java BFS Solution Explained

Learn how to solve LeetCode 102 Binary Tree Level Order Traversal using BFS and Queue in Java. Includes brute force intuition, optimized level order traversal, dry run, complexity analysis, interview explanation, and common mistakes.

Krishna Shrivastava
3 views
LinkedInGithubX
0
0
LeetCodeBinary Tree Level Order TraversalBFSQueueBinary TreeJavaTree TraversalMedium
LeetCode 102: Binary Tree Level Order Traversal – Java BFS Solution Explained
Listen to articleAudio version
Ad
Advertisement

Introduction

LeetCode 102 – Binary Tree Level Order Traversal is one of the most important Binary Tree traversal problems for coding interviews.

This problem introduces:

  1. Breadth First Search (BFS)
  2. Queue data structure
  3. Level-by-level traversal
  4. Tree traversal patterns
  5. Interview-level BFS thinking

Unlike DFS traversals like preorder, inorder, and postorder, this problem explores the tree level by level.

This traversal is widely used in:

  1. Graph traversal
  2. Shortest path problems
  3. Tree serialization
  4. Zigzag traversal
  5. BFS-based interview questions

Problem Link

🔗 https://leetcode.com/problems/binary-tree-level-order-traversal/

Problem Statement

Given the root of a binary tree, return the level order traversal of its nodes' values.

Traversal should happen:

Level by level
Left to right

Example

Input

root = [3,9,20,null,null,15,7]

Tree Structure:

3
/ \
9 20
/ \
15 7

Level Order Traversal

Level 1:

[3]

Level 2:

[9,20]

Level 3:

[15,7]

Final Output:

[[3],[9,20],[15,7]]

Understanding the Problem

The main challenge is:

Process nodes level by level.

This is exactly what:

Breadth First Search (BFS)

is designed for.

Why Queue is Used?

A queue follows:

First In First Out (FIFO)

This ensures:

  1. Nodes are processed in insertion order
  2. Parent nodes are processed before child nodes
  3. Levels are traversed correctly

Brute Force Intuition

One brute force idea is:

  1. Calculate height of tree
  2. Traverse each level separately
  3. Store nodes level by level

Brute Force Complexity

This approach becomes inefficient because:

  1. Each level traversal may revisit nodes
  2. Complexity may become:
O(N²)

for skewed trees.

Optimal BFS Intuition

Instead of traversing each level separately:

  1. Use a queue
  2. Process nodes level by level naturally

At every level:

  1. Store queue size
  2. Process exactly those many nodes
  3. Add children into queue
  4. Move to next level

Key BFS Observation

Before processing a level:

int size = queue.size();

This tells us:

How many nodes belong to the current level.

BFS Algorithm

Steps

1. Initialize Queue

Insert root node.

2. Process Until Queue Becomes Empty

While queue is not empty:

  1. Find current level size
  2. Traverse current level
  3. Store values
  4. Push child nodes

3. Store Current Level

After processing one level:

ans.add(levelList);

Java BFS Solution

/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* }
*/

class Solution {

public List<List<Integer>> levelOrder(TreeNode root) {

List<List<Integer>> ans = new ArrayList<>();

Queue<TreeNode> queue = new LinkedList<>();

if(root == null)
return ans;

queue.offer(root);

while(!queue.isEmpty()) {

int size = queue.size();

List<Integer> level = new ArrayList<>();

for(int i = 0; i < size; i++) {

root = queue.poll();

level.add(root.val);

if(root.left != null)
queue.offer(root.left);

if(root.right != null)
queue.offer(root.right);
}

ans.add(level);
}

return ans;
}
}

Dry Run

Input

root = [3,9,20,null,null,15,7]

Tree:

3
/ \
9 20
/ \
15 7

Initial Queue

[3]

Level 1

Queue size:

1

Process:

3

Add children:

9, 20

Level result:

[3]

Queue now:

[9,20]

Level 2

Queue size:

2

Process:

9, 20

Add children:

15, 7

Level result:

[9,20]

Queue now:

[15,7]

Level 3

Queue size:

2

Process:

15, 7

Level result:

[15,7]

Queue becomes empty.

Final Answer

[[3],[9,20],[15,7]]

Time Complexity Analysis

Time Complexity

O(N)

Every node is visited exactly once.

Space Complexity

O(N)

Queue may store an entire level of nodes.

DFS Alternative Approach

This problem can also be solved using DFS recursion.

Idea:

  1. Pass current level during recursion
  2. Create new list when level appears first time
  3. Add node into correct level list

Java DFS Solution

class Solution {

public void dfs(TreeNode root,
int level,
List<List<Integer>> ans) {

if(root == null)
return;

if(level == ans.size()) {
ans.add(new ArrayList<>());
}

ans.get(level).add(root.val);

dfs(root.left, level + 1, ans);

dfs(root.right, level + 1, ans);
}

public List<List<Integer>> levelOrder(TreeNode root) {

List<List<Integer>> ans = new ArrayList<>();

dfs(root, 0, ans);

return ans;
}
}

BFS vs DFS for Level Order Traversal

ApproachAdvantagesDisadvantages
BFSNatural level traversalUses queue
DFSRecursive solutionSlightly harder intuition

Interview Explanation

In interviews, explain:

Level order traversal is a BFS problem because we process nodes level by level. A queue naturally supports this traversal order.

This demonstrates strong BFS understanding.

Common Mistakes

1. Forgetting Queue Size

Without storing:

int size = queue.size();

levels cannot be separated correctly.

2. Using DFS Incorrectly

Simple DFS alone does not guarantee level ordering.

3. Forgetting Null Check

Always handle:

if(root == null)

FAQs

Q1. Why is BFS preferred here?

Because BFS naturally processes nodes level by level.

Q2. Can this problem be solved recursively?

Yes.

Using DFS with level tracking.

Q3. What data structure is mainly used?

Queue.

Q4. Is Level Order Traversal important?

Yes.

It is one of the most frequently asked BFS tree problems.

Related Problems

After mastering this problem, practice:

  1. Binary Tree Zigzag Level Order Traversal
  2. Average of Levels in Binary Tree
  3. Right Side View of Binary Tree
  4. Binary Tree Vertical Order Traversal
  5. Maximum Depth of Binary Tree

Conclusion

LeetCode 102 is one of the most important BFS tree traversal problems.

It teaches:

  1. BFS traversal
  2. Queue usage
  3. Level-by-level processing
  4. Tree traversal fundamentals

The key idea is:

Use queue size to separate levels.

Once this intuition becomes clear, many BFS-based tree interview problems become much easier.

Related Articles

Queue Data Structure Complete Guide - Java Explained With All Operations

Queue Data Structure Complete Guide - Java Explained With All Operations

Learn everything about Queue data structure in Java. Includes types of queues, all operations, real life examples, time & space complexity, and top LeetCode problems to practice.

Read Article
LeetCode 144: Binary Tree Preorder Traversal – Java Recursive & Iterative Solution Explained

LeetCode 144: Binary Tree Preorder Traversal – Java Recursive & Iterative Solution Explained

Learn how to solve LeetCode 144 Binary Tree Preorder Traversal using Recursive and Iterative approaches in Java. Includes traversal intuition, stack-based solution, dry run, complexity analysis, interview explanation, and common mistakes.

Read Article
LeetCode 94: Binary Tree Inorder Traversal – Java Recursive & Iterative Solution Explained

LeetCode 94: Binary Tree Inorder Traversal – Java Recursive & Iterative Solution Explained

Learn how to solve LeetCode 94 Binary Tree Inorder Traversal using Recursive and Iterative approaches in Java. Includes tree traversal intuition, dry run, stack-based solution, complexity analysis, interview tips, and common mistakes.

Read Article
LeetCode 145: Binary Tree Postorder Traversal – Java Recursive & Iterative Solution Explained

LeetCode 145: Binary Tree Postorder Traversal – Java Recursive & Iterative Solution Explained

Learn how to solve LeetCode 145 Binary Tree Postorder Traversal using Recursive and Iterative approaches in Java. Includes traversal intuition, stack-based solution, dry run, complexity analysis, interview explanation, and common mistakes.

Read Article
Ai Assistant Kas