Tree Traversal Level Order BFS in DSA Javascript - 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

↓

Queue empty -> traversal done

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

Execution Sample

DSA Javascript

function levelOrder(root) {
  const result = [];
  const queue = [];
  if (root) 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;
}

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

Execution Table

Step	Operation	Nodes in Queue (values)	Node Visited	Queue Changes	Visual State (Tree nodes visited)
1	Start with root	[1]	None	Add root (1) to queue	[]
2	Dequeue node	[1]	1	Remove 1 from queue	[1]
3	Visit node 1	[]	1	Add children 2, 3 to queue	[1]
4	Dequeue node	[2, 3]	2	Remove 2 from queue	[1, 2]
5	Visit node 2	[3]	2	Add children 4, 5 to queue	[1, 2]
6	Dequeue node	[3, 4, 5]	3	Remove 3 from queue	[1, 2, 3]
7	Visit node 3	[4, 5]	3	Add children 6, 7 to queue	[1, 2, 3]
8	Dequeue node	[4, 5, 6, 7]	4	Remove 4 from queue	[1, 2, 3, 4]
9	Visit node 4	[5, 6, 7]	4	No children to add	[1, 2, 3, 4]
10	Dequeue node	[5, 6, 7]	5	Remove 5 from queue	[1, 2, 3, 4, 5]
11	Visit node 5	[6, 7]	5	No children to add	[1, 2, 3, 4, 5]
12	Dequeue node	[6, 7]	6	Remove 6 from queue	[1, 2, 3, 4, 5, 6]
13	Visit node 6	[7]	6	No children to add	[1, 2, 3, 4, 5, 6]
14	Dequeue node	[7]	7	Remove 7 from queue	[1, 2, 3, 4, 5, 6, 7]
15	Visit node 7	[]	7	No children to add	[1, 2, 3, 4, 5, 6, 7]
16	Queue empty	[]	None	Traversal complete	[1, 2, 3, 4, 5, 6, 7]

💡 Queue is empty, all nodes visited in level order

Variable Tracker

Variable	Start	After Step 1	After Step 3	After Step 5	After Step 7	After Step 9	After Step 11	After Step 13	After Step 15	Final
queue	[]	[1]	[2, 3]	[3, 4, 5]	[4, 5, 6, 7]	[5, 6, 7]	[6, 7]	[7]	[]	[]
result	[]	[]	[1]	[1, 2]	[1, 2, 3]	[1, 2, 3, 4]	[1, 2, 3, 4, 5]	[1, 2, 3, 4, 5, 6]	[1, 2, 3, 4, 5, 6, 7]	[1, 2, 3, 4, 5, 6, 7]
node	null	1	2	3	4	5	6	7	null	null

Key Moments - 3 Insights

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

Because in the execution_table rows 3, 5, 7, etc., we first remove the node from the queue, then visit it, and only then add its children. This ensures nodes are visited level by level.

What happens if the tree is empty (root is null)?

The queue never gets any node added (see variable_tracker start state), so the while loop never runs and the traversal ends immediately with an empty result.

Why do we use a queue and not a stack for level order traversal?

A queue processes nodes in the order they were added (FIFO), which matches visiting nodes level by level. Using a stack (LIFO) would visit nodes depth-first, not level order.

Visual Quiz - 3 Questions

Look at the execution_table at Step 7, what nodes are currently in the queue?

A [3, 4, 5]

B [5, 6, 7]

C [4, 5, 6, 7]

D [2, 3]

💡 Hint

Check the 'Nodes in Queue (values)' column at Step 7 in the execution_table.

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

A Step 15

B Step 16

C Step 14

D Step 13

💡 Hint

Look for the step where 'Nodes in Queue' is empty and the exit_note says traversal complete.

If node 3 had no children, how would the queue change after Step 7?

A [4, 5]

B [4, 5, 6, 7]

C [4, 5, 6]

D [5, 6, 7]

💡 Hint

Refer to Step 7 where children of node 3 are added; removing them means fewer nodes added.

Concept Snapshot

Level Order Traversal (BFS) visits tree nodes level by level.
Use a queue to hold nodes to visit.
Start by adding root to queue.
While queue not empty: dequeue node, visit it, enqueue children.
Traversal ends when queue is empty.
Result is nodes visited in level order.

Full Transcript

Level Order Traversal uses a queue to visit nodes of a binary tree one level at a time. We start by adding the root node 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 repeats until the queue is empty, meaning all nodes have been visited in level order. The execution table shows each step, the queue contents, the node visited, and the visual state of visited nodes. The variable tracker follows the queue, result list, and current node through the steps. Key moments clarify why children are added after visiting, what happens if the tree is empty, and why a queue is used instead of a stack. The visual quiz tests understanding of queue contents at specific steps and effects of missing children. The concept snapshot summarizes the traversal process simply and clearly.