Tree Traversal Level Order BFS in DSA Typescript

Mental Model

Visit tree nodes level by level from top to bottom, left to right, like reading a book page by page.

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

      1
     / \
    2   3
   / \   \
  4   5   6

Queue: []
Visited order: []

Dry Run Walkthrough

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

Goal: Print nodes level by level: 1, then 2 and 3, then 4, 5, and 6

Step 1: Start with root node 1 in the queue

Queue: [1]
Visited order: []

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 order: [1]

Why: Visit current node and prepare to visit its children next

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

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

Why: Continue level order by visiting next node and enqueue its children

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

Queue: [4, 5, 6]
Visited order: [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 order: [1, 2, 3, 4]

Why: Visit leaf node with no children

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

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

Why: Visit leaf node with no children

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

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

Why: Visit last node, queue empty means traversal done

Result:

Visited order: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> null

Annotated Code

DSA Typescript

class TreeNode {
  val: number;
  left: TreeNode | null;
  right: TreeNode | null;
  constructor(val: number, left: TreeNode | null = null, right: TreeNode | null = null) {
    this.val = val;
    this.left = left;
    this.right = right;
  }
}

function levelOrderBFS(root: TreeNode | null): void {
  if (root === null) return;
  const queue: TreeNode[] = [];
  queue.push(root); // start with root

  while (queue.length > 0) {
    const current = queue.shift()!; // dequeue front node
    process.stdout.write(current.val + " -> "); // visit node

    if (current.left !== null) queue.push(current.left); // enqueue left child
    if (current.right !== null) queue.push(current.right); // enqueue right child
  }
  process.stdout.write("null\n"); // end of traversal
}

// Driver code to build tree and run traversal
const root = new TreeNode(1,
  new TreeNode(2, new TreeNode(4), new TreeNode(5)),
  new TreeNode(3, null, new TreeNode(6))
);

levelOrderBFS(root);

queue.push(root); // start with root

Initialize queue with root node to begin BFS

const current = queue.shift()!; // dequeue front node

Remove node from front of queue to visit it

process.stdout.write(current.val + " -> "); // visit node

Print current node value to show visitation order

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

Add left child to queue to visit in future

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

Add right child to queue to visit in future

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 largest 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)

Function returns immediately without printing anything

DSA Typescript

if (root === null) return;

Tree with only root node

Prints root value followed by null

DSA Typescript

queue.push(root); // start with root

Tree with nodes having only one child

Visits nodes in correct level order, skipping null children

DSA Typescript

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

When to Use This Pattern

When a problem asks to visit or process nodes level by level in a tree, use level order BFS because it naturally explores nodes one level at a time.

Common Mistakes

Mistake: Using recursion instead of a queue, which leads to depth-first traversal instead of level order
Fix: Use a queue data structure to hold nodes of the current level and process them in FIFO order

Mistake: Forgetting to check if children are null before adding to queue
Fix: Add null checks before enqueueing children to avoid errors

Mistake: Not printing 'null' at the end, making output unclear
Fix: Print 'null' after traversal to clearly mark the end

Summary

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

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.