Tree Traversal Level Order BFS in DSA Go

Mental Model

We visit tree nodes level by level from top to bottom, left to right, like reading lines in a book.

Analogy: Imagine a family photo where you first see parents, then children, then grandchildren, all in rows from top to bottom.

      1
     / \
    2   3
   / \   \
  4   5   6

Level order: 1 → 2 → 3 → 4 → 5 → 6 → null

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 from top to bottom, left to right

Step 1: Start with root node 1 in queue

Queue: [1]
Output: []

Why: We begin traversal from the root node

Step 2: Remove 1 from queue, print it, add its children 2 and 3 to queue

Queue: [2, 3]
Output: [1]

Why: Visit root, then prepare to visit next level nodes

Step 3: Remove 2 from queue, print it, add its children 4 and 5 to queue

Queue: [3, 4, 5]
Output: [1, 2]

Why: Visit left child of root, add its children for next level

Step 4: Remove 3 from queue, print it, add its child 6 to queue

Queue: [4, 5, 6]
Output: [1, 2, 3]

Why: Visit right child of root, add its child for next level

Step 5: Remove 4 from queue, print it, no children to add

Queue: [5, 6]
Output: [1, 2, 3, 4]

Why: Visit next node at level 3, no children to add

Step 6: Remove 5 from queue, print it, no children to add

Queue: [6]
Output: [1, 2, 3, 4, 5]

Why: Visit next node at level 3, no children to add

Step 7: Remove 6 from queue, print it, no children to add

Queue: []
Output: [1, 2, 3, 4, 5, 6]

Why: Visit last node, queue empty means traversal done

Result:

Output: 1 → 2 → 3 → 4 → 5 → 6 → null

Annotated Code

DSA Go

package main

import (
	"fmt"
)

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

func levelOrder(root *TreeNode) {
	if root == nil {
		return
	}
	queue := []*TreeNode{root} // start with root in queue
	for len(queue) > 0 {
		current := queue[0]       // get first node in queue
		queue = queue[1:]         // remove it from queue
		fmt.Printf("%d -> ", current.Val) // print current node
		if current.Left != nil {
			queue = append(queue, current.Left) // add left child
		}
		if current.Right != nil {
			queue = append(queue, current.Right) // add right child
		}
	}
	fmt.Print("null\n")
}

func main() {
	// build tree
	root := &TreeNode{Val: 1}
	root.Left = &TreeNode{Val: 2}
	root.Right = &TreeNode{Val: 3}
	root.Left.Left = &TreeNode{Val: 4}
	root.Left.Right = &TreeNode{Val: 5}
	root.Right.Right = &TreeNode{Val: 6}

	levelOrder(root)
}

queue := []*TreeNode{root} // start with root in queue

initialize queue with root node to start level order traversal

current := queue[0] // get first node in queue

select node at front of queue to visit

queue = queue[1:] // remove it from queue

remove visited node from queue to move forward

fmt.Printf("%d -> ", current.Val) // print current node

output current node value in traversal order

if current.Left != nil { queue = append(queue, current.Left) // add left child }

enqueue left child if exists for next level

if current.Right != nil { queue = append(queue, current.Right) // add right child }

enqueue right child if exists for next level

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 queue holds all nodes at one level

vs Alternative: Compared to recursive DFS, BFS uses a queue and visits nodes level by level, which can use more memory but is better for level-based problems

Edge Cases

empty tree (root is nil)

function returns immediately without printing

DSA Go

if root == nil {
	return
}

tree with single node

prints the single node value followed by null

DSA Go

queue := []*TreeNode{root} // start with root in queue

tree where some nodes have only one child

only existing children are added to queue, traversal continues correctly

DSA Go

if current.Left != nil {
	queue = append(queue, current.Left)
}

When to Use This Pattern

When a problem asks to visit nodes level by level or find shortest path in a tree, use level order BFS with a queue to process nodes in order.

Common Mistakes

Mistake: Forgetting to remove the current node from the queue after visiting
Fix: Remove the first element from the queue after processing it to avoid infinite loops

Mistake: Adding children to queue before printing current node
Fix: Print the current node before adding its children to maintain correct order

Summary

Visits all nodes in a tree level by level from top to bottom, left to right.

Use when you need to process or print nodes in order of their depth or level.

The key is to use a queue to hold nodes of the current level before moving to the next.