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.