Tree Traversal Level Order BFS in DSA Javascript

Mental Model

We visit tree nodes level by level, from top to bottom and left to right.

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

      1
     / \
    2   3
   / \   \
  4   5   6

Dry Run Walkthrough

Input: Binary tree: 1 with children 2 and 3; 2 has children 4 and 5; 3 has child 6

Goal: Visit nodes level by level and print their values in order

Step 1: Start with root node 1 in the queue

Queue: [1]
Visited: []

Why: We begin traversal from the root node

Step 2: Remove 1 from queue, visit it, add its children 2 and 3 to queue

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

Why: Visit current node and enqueue its children for next levels

Step 3: Remove 2 from queue, visit it, add its children 4 and 5 to queue

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

Why: Continue level order by visiting nodes left to right

Step 4: Remove 3 from queue, visit it, add its child 6 to queue

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

Why: Visit next node and enqueue its child

Step 5: Remove 4 from queue, visit it, no children to add

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

Why: Leaf node visited, no children to enqueue

Step 6: Remove 5 from queue, visit it, no children to add

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

Why: Leaf node visited, no children to enqueue

Step 7: Remove 6 from queue, visit it, no children to add

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

Why: Last node visited, queue empty, traversal done

Result:

Visited nodes in order: 1 -> 2 -> 3 -> 4 -> 5 -> 6

Annotated Code

DSA Javascript

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

function levelOrderBFS(root) {
  if (!root) return [];
  const queue = [root];
  const result = [];

  while (queue.length > 0) {
    const node = queue.shift();
    result.push(node.val);

    if (node.left) queue.push(node.left);
    if (node.right) queue.push(node.right);
  }

  return result;
}

// Driver code
const 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);

const traversal = levelOrderBFS(root);
console.log(traversal.join(' -> ') + ' -> null');

if (!root) return [];

handle empty tree by returning empty list

const queue = [root];

initialize queue with root node to start BFS

while (queue.length > 0) {

loop until all nodes are visited

const node = queue.shift();

remove front node from queue to visit it

result.push(node.val);

record visited node's value

if (node.left) queue.push(node.left);

enqueue left child if exists

if (node.right) queue.push(node.right);

enqueue right child if exists

Output

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

Complexity Analysis

Time: O(n) because each node is visited exactly once

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

vs Alternative: Compared to depth-first traversal which uses recursion stack, BFS uses a queue and visits nodes level by level, which is better for shortest path or level-based problems

Edge Cases

Empty tree (root is null)

Returns empty list immediately

DSA Javascript

if (!root) return [];

Tree with only root node

Returns list with single root value

DSA Javascript

while (queue.length > 0) { ... }

Tree with missing children

Only existing children are enqueued, no errors

DSA Javascript

if (node.left) queue.push(node.left);

When to Use This Pattern

When you need to visit nodes level by level or find shortest path in a tree, use level order BFS because it explores nodes in layers from top to bottom.

Common Mistakes

Mistake: Using recursion instead of a queue for level order traversal
Fix: Use a queue to process nodes in FIFO order for correct level order

Mistake: Not checking if left or right child exists before enqueueing
Fix: Add conditionals to enqueue children only if they are not null

Mistake: Using stack instead of queue, which results in DFS instead of BFS
Fix: Use a queue data structure to maintain correct visiting order

Summary

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

Use it when you want to process nodes in order of their depth or find shortest paths in trees.

The key is to use a queue to keep track of nodes to visit next in the correct order.