Tree Traversal Level Order BFS in DSA Java - Execution Trace

Concept Flow - Tree Traversal Level Order BFS

Start at root node

↓

Add root to queue

↓

While queue not empty

↓

Remove front node from queue

↓

Visit node (process value)

↓

Add left child to queue if exists

↓

Add right child to queue if exists

↓

Repeat loop until queue empty

↓

Traversal complete

Start from the root, use a queue to visit nodes level by level, adding children to the queue as you go.

Execution Sample

DSA Java

import java.util.Queue;
import java.util.LinkedList;

class Node {
  int val;
  Node left, right;
  Node(int v) { val = v; }
}

void levelOrder(Node root) {
  Queue<Node> q = new LinkedList<>();
  if (root == null) return;
  q.add(root);
  while (!q.isEmpty()) {
    Node curr = q.poll();
    System.out.print(curr.val + " ");
    if (curr.left != null) q.add(curr.left);
    if (curr.right != null) q.add(curr.right);
  }
}

Prints nodes of a binary tree level by level from left to right.

Execution Table

Step	Operation	Node Visited	Queue Before	Queue After	Visual State
1	Start - add root	None	[]	[1]	1
2	Remove front	1	[1]	[]	1
3	Add left child	1	[]	[2]	1 -> 2
4	Add right child	1	[2]	[2, 3]	1 -> 2 -> 3
5	Remove front	2	[2, 3]	[3]	1 -> 2 -> 3
6	Add left child	2	[3]	[3, 4]	1 -> 2 -> 3 -> 4
7	Add right child	2	[3, 4]	[3, 4, 5]	1 -> 2 -> 3 -> 4 -> 5
8	Remove front	3	[3, 4, 5]	[4, 5]	1 -> 2 -> 3 -> 4 -> 5
9	No children to add	3	[4, 5]	[4, 5]	1 -> 2 -> 3 -> 4 -> 5
10	Remove front	4	[4, 5]	[5]	1 -> 2 -> 3 -> 4 -> 5
11	No children to add	4	[5]	[5]	1 -> 2 -> 3 -> 4 -> 5
12	Remove front	5	[5]	[]	1 -> 2 -> 3 -> 4 -> 5
13	No children to add	5	[]	[]	1 -> 2 -> 3 -> 4 -> 5

💡 Queue is empty, traversal complete

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 5	After Step 8	After Step 10	Final
Queue	[]	[1]	[]	[3]	[4, 5]	[5]	[]
Node Visited	None	None	1	2	3	4	5

Key Moments - 3 Insights

Why do we add children to the queue after visiting a node?

Adding children after visiting ensures nodes are processed level by level, as shown in steps 3, 4, 6, and 7 in the execution_table.

Why does the loop stop when the queue is empty?

The queue holds nodes to visit; when empty (step 13), all nodes have been processed, so traversal ends.

Why do we remove nodes from the front of the queue?

Removing from the front ensures FIFO order, visiting nodes in the order they were added, preserving level order as seen in steps 2, 5, 8, 10, and 12.

Visual Quiz - 3 Questions

Look at the execution_table, what is the queue state after step 6?

A [3, 4, 5]

B [3, 4]

C [4, 5]

D [2, 3]

💡 Hint

Check the 'Queue After' column for step 6 in the execution_table.

At which step does the node with value 3 get visited?

A Step 5

B Step 10

C Step 8

D Step 12

💡 Hint

Look at the 'Node Visited' column in the execution_table.

If the node 2 had no children, how would the queue after step 7 change?

A [3]

B [3, 5]

C [3, 4, 5]

D [4, 5]

💡 Hint

Compare steps 6 and 7 in the execution_table and consider no children added for node 2.

Concept Snapshot

Level Order BFS Traversal:
- Use a queue to visit nodes level by level
- Start by adding root to queue
- While queue not empty:
  - Remove front node
  - Visit node
  - Add left child if exists
  - Add right child if exists
- Ends when queue empty

Full Transcript

Level Order BFS visits tree nodes level by level using a queue. Start by adding the root node to the queue. Then repeat: remove the front node, visit it, add its left and right children if they exist. Continue until the queue is empty, meaning all nodes are visited. This ensures nodes are processed in order of their depth in the tree.

Practice

1. What does Level Order Traversal (BFS) of a binary tree do?

easy

A. Visits nodes in random order

B. Visits nodes in left subtree, then root, then right subtree

C. Visits nodes level by level from top to bottom, left to right

D. Visits nodes in right subtree, then root, then left subtree

Solution

1. Step 1: Understand Level Order Traversal

   Level order traversal visits nodes level by level starting from the root, moving left to right at each level.

2. Step 2: Compare with other traversals

   Other traversals like inorder or postorder do not visit nodes level-wise but follow subtree orders.

3. Final Answer:

   Visits nodes level by level from top to bottom, left to right -> Option C

4. Quick Check:

   Level Order = BFS = top-down, left-right [OK]

Hint: Level order means visit nodes by levels, left to right [OK]

Common Mistakes:

• Confusing level order with inorder or preorder traversal
• Thinking traversal is random
• Mixing left and right subtree orders

2. Which Java code snippet correctly initializes a queue for level order traversal of a binary tree?

easy

A. Queue<TreeNode> queue = new ArrayList<>();

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

C. List<TreeNode> queue = new LinkedList<>();

D. Stack<TreeNode> queue = new Stack<>();

Solution

1. Step 1: Identify correct queue initialization

   Java's Queue interface is implemented by LinkedList, so Queue<TreeNode> queue = new LinkedList<>() is correct.

2. Step 2: Check other options

   ArrayList does not implement Queue, List is not a Queue, and Stack is LIFO, not FIFO needed for BFS.

3. Final Answer:

   Queue<TreeNode> queue = new LinkedList<>(); -> Option B

4. Quick Check:

   Queue for BFS = LinkedList implementation [OK]

Hint: Use LinkedList to implement Queue for BFS in Java [OK]

Common Mistakes:

• Using ArrayList instead of Queue
• Using Stack which is LIFO, not FIFO
• Declaring List instead of Queue

3. What is the output of the following Java code performing level order traversal on this tree?

    1
   / \
  2   3
 / \
4   5

// Code snippet:
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
  TreeNode node = queue.poll();
  System.out.print(node.val + " ");
  if (node.left != null) queue.add(node.left);
  if (node.right != null) queue.add(node.right);
}

medium

A. 1 2 3 4 5

B. 1 3 2 5 4

C. 4 5 2 3 1

D. 2 4 5 1 3

Solution

1. Step 1: Trace the queue operations

   Start with root (1). Print 1, add children 2 and 3. Then print 2, add 4 and 5. Then print 3 (no children). Then print 4 and 5.

2. Step 2: Write output sequence

   Output is: 1 2 3 4 5

3. Final Answer:

   1 2 3 4 5 -> Option A

4. Quick Check:

   Level order output = 1 2 3 4 5 [OK]

Hint: Print nodes as you dequeue in BFS order [OK]

Common Mistakes:

• Mixing preorder or inorder output with level order
• Adding children in wrong order
• Printing before adding children

4. Identify the bug in this Java code snippet for level order traversal:

Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
  TreeNode node = queue.peek();
  System.out.print(node.val + " ");
  if (node.left != null) queue.add(node.left);
  if (node.right != null) queue.add(node.right);
}

medium

A. Using peek() instead of poll() causes infinite loop

B. Not checking if root is null

C. Adding children after printing node value

D. Queue should be Stack for BFS

Solution

1. Step 1: Understand peek() vs poll()

   peek() returns the front element but does not remove it, so the queue never empties.

2. Step 2: Effect on loop

   Since queue is never emptied, while loop runs infinitely printing the same node repeatedly.

3. Final Answer:

   Using peek() instead of poll() causes infinite loop -> Option A

4. Quick Check:

   poll() removes front, peek() does not [OK]

Hint: Use poll() to remove nodes, not peek() [OK]

Common Mistakes:

• Confusing peek() and poll()
• Ignoring null root check
• Using Stack instead of Queue

5. Given a binary tree, how can you modify level order traversal to print nodes level by level on separate lines in Java?

hard

A. Print nodes as they are dequeued without tracking levels

B. Use recursion to print nodes in preorder with newlines

C. Use a stack to reverse the order and print levels bottom-up

D. Use a queue and track the number of nodes at each level, printing a newline after each level

Solution

1. Step 1: Track nodes per level using queue size

   At each iteration, get the current queue size which equals nodes at that level. Process exactly that many nodes, then print newline.

2. Step 2: Print nodes level-wise

   This ensures nodes of one level print on one line, then move to next line for next level.

3. Final Answer:

   Use a queue and track the number of nodes at each level, printing a newline after each level -> Option D

4. Quick Check:

   Queue size = nodes per level for line breaks [OK]

Hint: Use queue size to separate levels during BFS [OK]

Common Mistakes:

• Using recursion which is not level order
• Using stack which reverses order
• Not tracking level size, so no line breaks