Tree Traversal Level Order BFS in DSA Java

Mental Model

We visit tree nodes level by level from top to bottom, left to right, like reading lines in a book.

Analogy: Imagine a group of people standing in rows. You greet everyone in the first row before moving to the next row.

      1
     / \
    2   3
   / \   \
  4   5   6

Levels:
Level 0: 1
Level 1: 2 -> 3
Level 2: 4 -> 5 -> 6

Dry Run Walkthrough

Input: Binary tree: 1 as root, 2 and 3 as children of 1, 4 and 5 as children of 2, 6 as right child of 3

Goal: Print nodes level by level: 1 -> 2 -> 3 -> 4 -> 5 -> 6

Step 1: Start with root node 1 in the queue

Queue: [1]
Output: []

Why: We begin traversal from the root

Step 2: Remove 1 from queue, add its value to output, enqueue its children 2 and 3

Queue: [2, 3]
Output: [1]

Why: Visit root and prepare to visit next level

Step 3: Remove 2 from queue, add its value to output, enqueue its children 4 and 5

Queue: [3, 4, 5]
Output: [1, 2]

Why: Visit left child of root and enqueue next level nodes

Step 4: Remove 3 from queue, add its value to output, enqueue its right child 6

Queue: [4, 5, 6]
Output: [1, 2, 3]

Why: Visit right child of root and enqueue next level node

Step 5: Remove 4 from queue, add its value to output, no children to enqueue

Queue: [5, 6]
Output: [1, 2, 3, 4]

Why: Visit leftmost node at level 2

Step 6: Remove 5 from queue, add its value to output, no children to enqueue

Queue: [6]
Output: [1, 2, 3, 4, 5]

Why: Visit next node at level 2

Step 7: Remove 6 from queue, add its value to output, no children to enqueue

Queue: []
Output: [1, 2, 3, 4, 5, 6]

Why: Visit last node at level 2

Result:

Output: 1 -> 2 -> 3 -> 4 -> 5 -> 6

Annotated Code

DSA Java

import java.util.*;

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int val) { this.val = val; }
}

public class LevelOrderTraversal {
    public static List<Integer> levelOrder(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) return result;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root); // enqueue root
        while (!queue.isEmpty()) {
            TreeNode current = queue.poll(); // dequeue front
            result.add(current.val); // add value to output
            if (current.left != null) queue.add(current.left); // enqueue left child
            if (current.right != null) queue.add(current.right); // enqueue right child
        }
        return result;
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);
        root.right.right = new TreeNode(6);

        List<Integer> traversal = levelOrder(root);
        for (int val : traversal) {
            System.out.print(val + " -> ");
        }
        System.out.print("null\n");
    }
}

queue.add(root); // enqueue root

start traversal by adding root to queue

TreeNode current = queue.poll(); // dequeue front

remove front node from queue to visit

result.add(current.val); // add value to output

record current node's value

if (current.left != null) queue.add(current.left); // enqueue left child

add left child to queue if exists

if (current.right != null) queue.add(current.right); // enqueue right child

add right child to queue if exists

Output

1 -> 2 -> 3 -> 4 -> 5 -> 6 -> null

Complexity Analysis

Time: O(n) because we visit each of the n nodes exactly once

Space: O(n) because in the worst case the queue holds all nodes at the largest level

vs Alternative: Compared to recursive depth-first traversals, BFS uses extra space for the queue but processes nodes level by level which is useful for certain problems

Edge Cases

Empty tree (root is null)

Returns empty list immediately without errors

DSA Java

if (root == null) return result;

Tree with only root node

Returns list with single root value

DSA Java

queue.add(root); // enqueue root

Tree with missing children at some nodes

Skips null children safely without adding to queue

DSA Java

if (current.left != null) queue.add(current.left);

When to Use This Pattern

When a problem asks to process or print tree nodes level by level or in order of closeness to root, use level order BFS traversal with a queue.

Common Mistakes

Mistake: Forgetting to check if left or right child is null before adding to queue
Fix: Add null checks before enqueueing children to avoid errors

Mistake: Using stack or recursion which leads to depth-first order instead of level order
Fix: Use a queue to ensure breadth-first order

Summary

Visits all nodes in a tree level by level from top to bottom, left to right.

Use when you need to process nodes in order of their distance from the root.

The key is to use a queue to hold nodes of the current level before moving to the next.

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