Tree Traversal Level Order BFS in DSA Java - Time & Space Complexity

Time Complexity: Tree Traversal Level Order BFS

O(n)

Understanding Time Complexity

We want to understand how the time needed to visit all nodes in a tree grows as the tree gets bigger.

How does the number of steps change when we use level order traversal (BFS)?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

public void levelOrderTraversal(TreeNode root) {
    if (root == null) return;
    Queue 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);
    }
}
    

This code visits each node in the tree level by level, from top to bottom and left to right.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Visiting each node once and adding its children to the queue.
• How many times: Exactly once per node in the tree.

How Execution Grows With Input

As the number of nodes grows, the steps to visit all nodes grow at the same rate.

Input Size (n)	Approx. Operations
10	About 10 visits and queue operations
100	About 100 visits and queue operations
1000	About 1000 visits and queue operations

Pattern observation: The number of operations grows directly with the number of nodes.

Final Time Complexity

Time Complexity: O(n)

This means the time to complete the traversal grows linearly with the number of nodes in the tree.

Common Mistake

[X] Wrong: "Since we use a queue and loops, the time must be more than linear, maybe quadratic."

[OK] Correct: Each node is visited once and added/removed from the queue once, so operations scale directly with node count, not more.

Interview Connect

Understanding level order traversal time helps you explain how tree algorithms scale, a key skill in many coding challenges.

Self-Check

"What if the tree was very unbalanced, like a linked list? How would the time complexity change?"

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