Level-Order Traversal

Visit a tree breadth-first with a queue.

Algorithm

The canonical tree is 4(2(1,3),6(5,7)), so this Go DSA implementation can be compared directly with the rest of the DSA track.

level order Level-order traversal uses a queue to visit shallower nodes first.

Basic Implementation

                            basic.go
                        
Replay: real traced execution (multi-file project)

                            package main

import (
    "fmt"
    "strings"
)

type Node struct { value int; left *Node; right *Node }
func render(node *Node) string {
    if node == nil { return "_" }
    if node.left == nil && node.right == nil { return fmt.Sprintf("%d", node.value) }
    return fmt.Sprintf("%d(%s,%s)", node.value, render(node.left), render(node.right))
}
func sampleTree() *Node {
    return &Node{4, &Node{2, &Node{1, nil, nil}, &Node{3, nil, nil}}, &Node{6, &Node{5, nil, nil}, &Node{7, nil, nil}}}
}
func listString(values []int) string {
    parts := []string{}
    for _, value := range values { parts = append(parts, fmt.Sprintf("%d", value)) }
    return "[" + strings.Join(parts, ", ") + "]"
}
func main() { queue := []*Node{sampleTree()}; output := []int{}; for len(queue) > 0 { node := queue[0]; queue = queue[1:]; output = append(output, node.value); if node.left != nil { queue = append(queue, node.left) }; if node.right != nil { queue = append(queue, node.right) } }; fmt.Println(listString(output)) }

                        
1tree ← 4(2(1,3),6(5,7)), queue ← [4]1package main⋯values this step4(2(1,3),6(5,7))tree[4]queue
2output ← [4], queue ← [2, 6]⋯21}22func main() { queue := []*Node{sampleTree()}; output := []int{}; for len(queue) > 0 { node := queue[0]; queue = queue[1:]; output = append(output, node.value); if node.left != nil { queue = append(queue, node.left) }; if node.right != nil { queue = append(queue, node.right) } }; fmt.Println(listString(output)) }values this step[4]output[2, 6]queue4dequeued
3output ← [4, 2], queue ← [6, 1, 3]⋯21}22func main() { queue := []*Node{sampleTree()}; output := []int{}; for len(queue) > 0 { node := queue[0]; queue = queue[1:]; output = append(output, node.value); if node.left != nil { queue = append(queue, node.left) }; if node.right != nil { queue = append(queue, node.right) } }; fmt.Println(listString(output)) }values this step[4, 2]output[6, 1, 3]queue2dequeued
4output ← [4, 2, 6], queue ← [1, 3, 5, 7]⋯21}22func main() { queue := []*Node{sampleTree()}; output := []int{}; for len(queue) > 0 { node := queue[0]; queue = queue[1:]; output = append(output, node.value); if node.left != nil { queue = append(queue, node.left) }; if node.right != nil { queue = append(queue, node.right) } }; fmt.Println(listString(output)) }values this step[4, 2, 6]output[1, 3, 5, 7]queue6dequeued
5output ← [4, 2, 6, 1], queue ← [3, 5, 7]⋯21}22func main() { queue := []*Node{sampleTree()}; output := []int{}; for len(queue) > 0 { node := queue[0]; queue = queue[1:]; output = append(output, node.value); if node.left != nil { queue = append(queue, node.left) }; if node.right != nil { queue = append(queue, node.right) } }; fmt.Println(listString(output)) }values this step[4, 2, 6, 1]output[3, 5, 7]queue1dequeued
6output ← [4, 2, 6, 1, 3], queue ← [5, 7]⋯21}22func main() { queue := []*Node{sampleTree()}; output := []int{}; for len(queue) > 0 { node := queue[0]; queue = queue[1:]; output = append(output, node.value); if node.left != nil { queue = append(queue, node.left) }; if node.right != nil { queue = append(queue, node.right) } }; fmt.Println(listString(output)) }values this step[4, 2, 6, 1, 3]output[5, 7]queue3dequeued
7output ← [4, 2, 6, 1, 3, 5], queue ← [7]⋯21}22func main() { queue := []*Node{sampleTree()}; output := []int{}; for len(queue) > 0 { node := queue[0]; queue = queue[1:]; output = append(output, node.value); if node.left != nil { queue = append(queue, node.left) }; if node.right != nil { queue = append(queue, node.right) } }; fmt.Println(listString(output)) }values this step[4, 2, 6, 1, 3, 5]output[7]queue5dequeued
8output ← [4, 2, 6, 1, 3, 5, 7], queue ← []⋯21}22func main() { queue := []*Node{sampleTree()}; output := []int{}; for len(queue) > 0 { node := queue[0]; queue = queue[1:]; output = append(output, node.value); if node.left != nil { queue = append(queue, node.left) }; if node.right != nil { queue = append(queue, node.right) } }; fmt.Println(listString(output)) }values this step[4, 2, 6, 1, 3, 5, 7]output[]queue7dequeued
9if node.left == nil && node.right == nil { return fmt.Sprintf("%d", no…⋯10if node == nil { return "_" }11if node.left == nil && node.right == nil { return fmt.Sprintf("%d", node.value) }12return fmt.Sprintf("%d(%s,%s)", node.value, render(node.left), render(node.right))⋯values this step[4, 2, 6, 1, 3, 5, 7]output

Complexity

Time: O(n)
Space: O(w) queue space

Implementation notes

Go uses type Node struct { value int; left *Node; right *Node }; the queue stores *Node pointers, not node copies.
queue := []*Node{sampleTree()} seeds the traversal with the root pointer, and output := []int{} grows by append(output, node.value).
Each loop reads the front with node := queue[0] and advances the slice header with queue = queue[1:]; retained queue slices can keep the old backing array alive, but this replay drains the queue immediately.
Child pointers are enqueued only after nil checks: if node.left != nil { queue = append(queue, node.left) } and the same for right, preserving left-before-right order.
The trace records queue/output states as [4], then output [4] with queue [2, 6], then [4, 2] with [6, 1, 3], then [4, 2, 6] with [1, 3, 5, 7], and finally [4, 2, 6, 1, 3, 5, 7] with an empty queue.
listString converts each int with fmt.Sprintf("%d", value) and strings.Join; fmt.Println(listString(output)) prints [4, 2, 6, 1, 3, 5, 7].