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

type Node struct {
  Val int
  Left, Right *Node
}

func LevelOrder(root *Node) []int {
  if root == nil {
    return []int{}
  }
  queue := []*Node{root}
  var result []int
  for len(queue) > 0 {
    node := queue[0]
    queue = queue[1:]
    result = append(result, node.Val)
    if node.Left != nil {
      queue = append(queue, node.Left)
    }
    if node.Right != nil {
      queue = append(queue, node.Right)
    }
  }
  return result
}

This code visits each node in the 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	1	[]	[1]	1 / \ 2 3
2	Dequeue node	1	[1]	[]	1 / \ 2 3
3	Visit node	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	[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	[4,5]	[4,5]	Visited: 1, 2, 3
12	Enqueue left child	3	[4,5]	[4,5]	No left child
13	Enqueue right child	3	[4,5]	[4,5,6]	Queue: 4 -> 5 -> 6
14	Dequeue node	4	[4,5,6]	[5,6]	Queue: 5 -> 6
15	Visit node	4	[5,6]	[5,6]	Visited: 1, 2, 3, 4
16	Enqueue left child	4	[5,6]	[5,6]	No left child
17	Enqueue right child	4	[5,6]	[5,6]	No right child
18	Dequeue node	5	[5,6]	[6]	Queue: 6
19	Visit node	5	[6]	[6]	Visited: 1, 2, 3, 4, 5
20	Enqueue left child	5	[6]	[6]	No left child
21	Enqueue right child	5	[6]	[6]	No right child
22	Dequeue node	6	[6]	[]	Queue: empty
23	Visit node	6	[]	[]	Visited: 1, 2, 3, 4, 5, 6
24	Enqueue left child	6	[]	[]	No left child
25	Enqueue right child	6	[]	[]	No right child
26	Queue empty	-	[]	[]	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	After Step 25	Final
queue	[]	[1]	[2,3]	[3,4,5]	[4,5,6]	[5,6]	[6]	[]	[]
visited_nodes	[]	[1]	[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]

Key Moments - 3 Insights

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

Because in BFS, we visit nodes level by level. Adding children after visiting ensures we process all nodes at the current level before moving deeper. See steps 4,5 and 8,9 where children are added after visiting.

Why does the loop stop when the queue is empty?

The queue holds nodes to visit. When empty, no nodes remain to process, so traversal is complete. This is shown at step 26 where the queue is empty and traversal ends.

Why do we remove the node from the front of the queue each time?

Removing from the front ensures nodes are visited in the order they were added, preserving level order. See steps 2,6,10 where nodes are dequeued from the front.

Visual Quiz - 3 Questions

Look at the execution table, what is the queue after step 9?

A [4,5]

B [3,4,5]

C [2,3]

D [5,6]

💡 Hint

Check the 'Queue After' column at step 9 in the execution_table.

At which step does the queue become empty?

A Step 26

B Step 18

C Step 22

D Step 2

💡 Hint

Look for the step where 'Queue After' is empty and traversal ends.

If node 3 had no right child, how would the queue after step 13 change?

A [5,6]

B [4,5,6]

C [4,5]

D [3,4,5]

💡 Hint

Step 13 shows enqueueing right child of node 3; if missing, queue won't include 6.

Concept Snapshot

Level Order BFS visits tree nodes level by level.
Use a queue to hold nodes to visit.
Start by enqueueing root.
While queue not empty: dequeue, visit, enqueue children.
Stops when queue is empty.
Result is nodes in level order.

Full Transcript

Level Order BFS starts at the root node and uses a queue to visit nodes level by level. Initially, the root is added to the queue. Then, while the queue is not empty, the node at the front is removed and visited. Its children, if any, are added to the back of the queue. This process repeats until no nodes remain in the queue, meaning all nodes have been visited in level order. The execution table shows each step, including queue changes and visited nodes. The variable tracker records the queue and visited nodes after key steps. Key moments clarify why children are added after visiting, why the loop stops when the queue is empty, and why nodes are dequeued from the front to maintain order. The visual quiz tests understanding of queue states and effects of missing children. The concept snapshot summarizes the BFS traversal process clearly and simply.