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.

Practice

1. What does the Level Order Traversal (BFS) of a binary tree do?

easy

A. Visits nodes in preorder (root, left, right)

B. Visits nodes level by level from top to bottom, left to right

C. Visits nodes in inorder (left, root, right)

D. Visits nodes in postorder (left, right, root)

Solution

1. Step 1: Understand Level Order Traversal

   Level Order Traversal visits nodes level by level starting from the root, moving left to right on each level.

2. Step 2: Compare with other traversals

   Preorder, inorder, and postorder are depth-first traversals, not level by level.

3. Final Answer:

   Visits nodes level by level from top to bottom, left to right -> Option B

4. Quick Check:

   Level Order = BFS = top to bottom, left to right [OK]

Hint: Level order means visit nodes by levels, not depth [OK]

Common Mistakes:

• Confusing level order with preorder traversal
• Thinking BFS visits nodes depth-first
• Mixing up traversal orders

2. Which of the following TypeScript code snippets correctly initializes a queue for BFS traversal?

easy

A. const queue: TreeNode[] = []; queue.push(root);

B. const queue = new Set(); queue.add(root);

C. const queue = new Map(); queue.set(0, root);

D. const queue = {}; queue.enqueue(root);

Solution

1. Step 1: Identify correct queue initialization

   In TypeScript, an array can be used as a queue with push and shift methods.

2. Step 2: Check each option

   const queue: TreeNode[] = []; queue.push(root); uses an array and push, which is correct. const queue = new Set(); queue.add(root); uses Set which is unordered. const queue = new Map(); queue.set(0, root); uses Map which is key-value, not queue. const queue = {}; queue.enqueue(root); uses an object with enqueue method which does not exist.

3. Final Answer:

   const queue: TreeNode[] = []; queue.push(root); -> Option A

4. Quick Check:

   Array with push/shift = queue [OK]

Hint: Use array with push and shift for queue in TypeScript [OK]

Common Mistakes:

• Using Set or Map instead of array for queue
• Calling non-existent enqueue method on object
• Not initializing queue before use

3. Given the binary tree below, what is the output of the level order traversal?

    1
   / \
  2   3
 /   / \
4   5   6

function levelOrder(root: TreeNode | null): number[] { if (!root) return []; const queue: TreeNode[] = [root]; const result: number[] = []; 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; }

medium

A. [1, 2, 4, 3, 5, 6]

B. [1, 3, 2, 6, 5, 4]

C. [1, 2, 3, 4, 5, 6]

D. [4, 2, 5, 3, 6, 1]

Solution

1. Step 1: Trace the queue and result arrays

   Start with queue = [1], result = []. Remove 1, add to result: [1]. Add children 2 and 3 to queue: [2,3]. Remove 2, add to result: [1,2]. Add child 4: queue = [3,4]. Remove 3, add to result: [1,2,3]. Add children 5 and 6: queue = [4,5,6]. Remove 4, add to result: [1,2,3,4]. No children. Remove 5, add to result: [1,2,3,4,5]. No children. Remove 6, add to result: [1,2,3,4,5,6]. No children.

2. Step 2: Confirm final output

   The final result array is [1, 2, 3, 4, 5, 6].

3. Final Answer:

   [1, 2, 3, 4, 5, 6] -> Option C

4. Quick Check:

   Level order visits nodes level-wise: [1,2,3,4,5,6] [OK]

Hint: Follow queue order: push children left then right [OK]

Common Mistakes:

• Mixing left and right child order
• Confusing preorder with level order output
• Forgetting to add children to queue

4. The following TypeScript code for level order traversal has a bug. What is the error?

function levelOrder(root: TreeNode | null): number[] {
  const queue: TreeNode[] = [];
  const result: number[] = [];
  queue.push(root!);
  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;
}

medium

A. It pushes children after adding node to result

B. It uses shift() instead of pop() on the queue

C. It returns result before the loop ends

D. It does not check if root is null before pushing

Solution

1. Step 1: Analyze root null check

   The code pushes root! without checking if root is null. If root is null, queue contains null and node.val will cause runtime error.

2. Step 2: Verify other parts

   Using shift() is correct for queue. Adding children after node is correct. Return is after loop ends.

3. Final Answer:

   It does not check if root is null before pushing -> Option D

4. Quick Check:

   Always check root null before queue push [OK]

Hint: Check root null before queue push to avoid errors [OK]

Common Mistakes:

• Ignoring null root check
• Confusing shift() with pop() for queue
• Misplacing return statement

5. You want to print the level order traversal of a binary tree but separate each level on a new line. Which approach correctly achieves this in TypeScript?

function levelOrderByLevel(root: TreeNode | null): number[][] {
  if (!root) return [];
  const result: number[][] = [];
  const queue: TreeNode[] = [root];
  while (queue.length > 0) {
    const levelSize = queue.length;
    const currentLevel: number[] = [];
    for (let i = 0; i < levelSize; i++) {
      const node = queue.shift()!;
      currentLevel.push(node.val);
      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }
    result.push(currentLevel);
  }
  return result;
}

hard

A. Use a loop for each level size, collect nodes, then push to result

B. Push all nodes to result as a flat array without levels

C. Use recursion to print nodes without queue

D. Add all children to queue before processing current level

Solution

1. Step 1: Understand level separation logic

   Using levelSize to track nodes at current level allows processing nodes level by level.

2. Step 2: Check code correctness

   Loop runs levelSize times, collects node values in currentLevel, adds children to queue for next level, then pushes currentLevel to result.

3. Final Answer:

   Use a loop for each level size, collect nodes, then push to result -> Option A

4. Quick Check:

   Track level size, process nodes per level [OK]

Hint: Use queue length to separate levels in BFS [OK]

Common Mistakes:

• Not separating levels, returning flat array
• Using recursion instead of queue for BFS
• Adding children before processing current level nodes