Tree Traversal Level Order BFS in DSA Java - Build from Scratch

Tree Traversal Level Order BFS

📖 Scenario: You are working with a simple family tree where each person can have children. You want to visit each family member level by level, starting from the oldest ancestor, to understand the family structure clearly.

🎯 Goal: Build a Java program that performs a level order traversal (Breadth-First Search) on a binary tree representing the family tree. You will create the tree, set up a queue for traversal, implement the BFS logic, and finally print the nodes level by level.

📋 What You'll Learn

Create a binary tree with exact nodes and structure

Use a queue to help with level order traversal

Implement the BFS traversal using a while loop

Print the nodes in level order separated by spaces

💡 Why This Matters

🌍 Real World

Level order traversal is used in many real-world applications like finding the shortest path in maps, scheduling tasks, and analyzing hierarchical data such as family trees or organizational charts.

💼 Career

Understanding BFS and tree traversal is essential for software engineers working with data structures, algorithms, and system design, especially in roles involving search algorithms, databases, and network analysis.

1

Create the binary tree nodes

Create a class called TreeNode with an integer val and two child nodes left and right. Then create the root node with value 1, its left child with value 2, and its right child with value 3. Also create the left child of node 2 with value 4 and the right child of node 2 with value 5.

DSA Java

// Define TreeNode class and create the tree nodes
// Your code here

Hint

Define the TreeNode class first. Then create the root and assign its children exactly as described.

2

Set up a queue for BFS traversal

Inside the main method, create a Queue<TreeNode> called queue using LinkedList<>(). Add the root node to the queue.

DSA Java

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

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

public class Main {
    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);

        // Create a queue and add root
        // Your code here
    }
}

Hint

Use Queue<TreeNode> queue = new LinkedList<>(); and then add the root node with queue.add(root);.

3

Implement the BFS traversal logic

Inside the main method, write a while loop that runs while queue is not empty. Inside the loop, remove the front node from queue into a variable called current. Then, if current.left is not null, add it to queue. Similarly, if current.right is not null, add it to queue. Also, print the value of current.val followed by a space inside the loop.

DSA Java

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

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

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

public class Main {
    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);

        Queue queue = new LinkedList();
        queue.add(root);

        // Implement BFS traversal loop
        // Your code here
    }
}

Hint

Use while (!queue.isEmpty()) to loop. Remove the front node with queue.remove(). Print its value. Add children if they exist.

4

Print the final level order traversal output

Run the program and observe the printed output. It should show the node values in level order separated by spaces.

DSA Java

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

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

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

public class Main {
    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);

        Queue queue = new LinkedList();
        queue.add(root);

        while (!queue.isEmpty()) {
            TreeNode current = queue.remove();
            System.out.print(current.val + " ");
            if (current.left != null) {
                queue.add(current.left);
            }
            if (current.right != null) {
                queue.add(current.right);
            }
        }
    }

// Run the program to see the output

Hint

The output should be the node values in level order separated by spaces: 1 2 3 4 5

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