Trees

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.

Basic Implementation

basic.go 
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)) }

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].
level order Level-order traversal uses a queue to visit shallower nodes first.