Tree Traversal Level Order BFS in DSA Typescript - Execution Trace

Concept Flow - Tree Traversal Level Order BFS

Start at root node

↓

Add root to queue

↓

While queue not empty

↓

Remove front node from queue

↓

Visit node (process value)

↓

Add left child to queue if exists

↓

Add right child to queue if exists

↓

Repeat loop

Start from the root, use a queue to visit nodes level by level, adding children to the queue as you go.

Execution Sample

DSA Typescript

class Node {
  constructor(public val: number, public left: Node | null = null, public right: Node | null = null) {}
}

function levelOrder(root: Node | null): number[] {
  const result: number[] = [];
  if (!root) return result;
  const queue: Node[] = [root];
  while (queue.length) {
    const node = queue.shift()!;
    result.push(node.val);
    if (node.left) queue.push(node.left);
    if (node.right) queue.push(node.right);
  }
  return result;
}

This code visits each node of a binary tree level by level using a queue and collects their values.

Execution Table

Step	Operation	Node Visited	Queue Before	Queue After	Visual State
1	Start with root	null	[]	[1]	1 / \ 2 3
2	Dequeue node	1	[1]	[]	1 / \ 2 3
3	Visit node 1	1	[]	[]	Visited: [1]
4	Enqueue left child	1	[]	[2]	Queue: [2]
5	Enqueue right child	1	[2]	[2,3]	Queue: [2,3]
6	Dequeue node	2	[2,3]	[3]	Queue: [3]
7	Visit node 2	2	[3]	[3]	Visited: [1,2]
8	Enqueue left child	2	[3]	[3,4]	Queue: [3,4]
9	Enqueue right child	2	[3,4]	[3,4,5]	Queue: [3,4,5]
10	Dequeue node	3	[3,4,5]	[4,5]	Queue: [4,5]
11	Visit node 3	3	[4,5]	[4,5]	Visited: [1,2,3]
12	Enqueue left child	3	[4,5]	[4,5]	Node 3 has no left child, no enqueue
13	Enqueue right child	3	[4,5]	[4,5]	Node 3 has no right child, no enqueue
14	Dequeue node	4	[4,5]	[5]	Queue: [5]
15	Visit node 4	4	[5]	[5]	Visited: [1,2,3,4]
16	Enqueue left child	4	[5]	[5]	Node 4 has no left child, no enqueue
17	Enqueue right child	4	[5]	[5]	Node 4 has no right child, no enqueue
18	Dequeue node	5	[5]	[]	Queue: []
19	Visit node 5	5	[]	[]	Visited: [1,2,3,4,5]
20	Enqueue left child	5	[]	[]	Node 5 has no left child, no enqueue
21	Enqueue right child	5	[]	[]	Node 5 has no right child, no enqueue
22	Queue empty	null	[]	[]	Traversal complete

💡 Queue is empty, all nodes visited

Variable Tracker

Variable	Start	After Step 1	After Step 5	After Step 9	After Step 13	After Step 17	After Step 21	Final
queue	[]	[1]	[2,3]	[3,4,5]	[4,5]	[5]	[]	[]
visited	[]	[]	[1]	[1,2]	[1,2,3]	[1,2,3,4]	[1,2,3,4,5]	[1,2,3,4,5]
current_node	null	1	1	2	3	4	5	null

Key Moments - 3 Insights

Why do we add children to the queue after visiting the node?

Because BFS visits nodes level by level, adding children after visiting ensures nodes on the same level are visited before going deeper. See steps 4,5 and 8,9 in execution_table.

Why does the queue start with the root node?

The root is the starting point of the tree. Adding it to the queue first (step 1) allows the algorithm to begin visiting nodes from the top level.

What happens when a node has no children?

No new nodes are added to the queue (steps 12,13,16,17,20,21). The queue shrinks until empty, ending traversal.

Visual Quiz - 3 Questions

Look at the execution_table, what is the queue after visiting node 2 (step 7)?

A [3,4]

B [3]

C [3,4,5]

D [2,3]

💡 Hint

Check the 'Queue After' column at step 7 and following enqueue steps 8 and 9.

At which step does the queue become empty, ending the traversal?

A Step 22

B Step 20

C Step 18

D Step 21

💡 Hint

Look for the step where 'Queue Before' and 'Queue After' are both empty and traversal ends.

If node 3 had a left child, how would the queue change after step 12?

A Queue would remove node 4 immediately

B Queue would remain the same as step 12

C It would add the left child to the queue after step 12

D Traversal would end earlier

💡 Hint

Step 12 shows no enqueue because node 3 has no left child; adding one would enqueue it here.

Concept Snapshot

Level Order BFS visits tree nodes level by level.
Use a queue starting with root.
Dequeue node, visit it, enqueue children.
Repeat until queue empty.
Result is nodes in breadth-first order.

Full Transcript

Level Order BFS traversal starts at the root node. We use a queue to keep track of nodes to visit. Initially, the root is added to the queue. Then, while the queue is not empty, we remove the front node, visit it by recording its value, and add its left and right children to the queue if they exist. This process continues until all nodes are visited and the queue is empty. The traversal visits nodes level by level, from left to right within each level.

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