Zigzag Level Order Traversal in DSA Go - Build from Scratch

Zigzag Level Order Traversal

📖 Scenario: Imagine you have a family tree represented as a binary tree. You want to visit each generation, but in a zigzag way: first generation from left to right, second from right to left, and so on. This helps you see the family members in a fun pattern.

🎯 Goal: Build a program that takes a binary tree and prints its nodes in zigzag level order traversal.

📋 What You'll Learn

Create a binary tree using the given TreeNode struct

Use a queue to traverse the tree level by level

Alternate the order of nodes at each level (left to right, then right to left)

Print the final zigzag traversal as a slice of slices

💡 Why This Matters

🌍 Real World

Zigzag traversal is useful in scenarios like visualizing hierarchical data with alternating directions for better readability.

💼 Career

Understanding tree traversals and queue usage is essential for software engineering roles involving data structures, algorithms, and system design.

1

Create the binary tree

Create the binary tree nodes using the TreeNode struct with these exact values and connections: root node with Val: 1, left child with Val: 2, right child with Val: 3, left child of node 2 with Val: 4, and right child of node 3 with Val: 5. Assign the root node to a variable called root.

DSA Go

package main

import "fmt"

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

func main() {
    // Create the binary tree nodes and assign to root
    // Your code here
}

Hint

Use the &TreeNode{Val: value} syntax to create nodes and assign children using Left and Right fields.

2

Initialize traversal variables

Create a variable called results as a slice of slices of integers to store the final zigzag traversal. Also create a variable called leftToRight of type bool and set it to true to track the direction of traversal.

DSA Go

package main

import "fmt"

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

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

    // Create results slice and leftToRight boolean
    // Your code here
}

Hint

Use results := [][]int{} to create an empty slice of slices and leftToRight := true to start with left to right direction.

3

Implement zigzag level order traversal

Use a queue slice of *TreeNode called queue initialized with root. Use a for loop that runs while len(queue) > 0. Inside the loop, create a slice level to store node values of the current level. Use a for loop to iterate exactly len(queue) times, popping nodes from the front of queue. Append their values to level. Add their children to the end of queue. After the inner loop, if leftToRight is false, reverse the level slice. Append level to results. Flip the leftToRight boolean to its opposite value.

DSA Go

package main

import "fmt"

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

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

    results := [][]int{}
    leftToRight := true

    // Implement zigzag traversal using queue and loops
    // Your code here
}

Hint

Use a queue slice to hold nodes. Pop from front and append children to back. Reverse the level slice when direction is right to left.

4

Print the zigzag traversal result

Print the results variable using fmt.Println(results) to display the zigzag level order traversal.

DSA Go

package main

import "fmt"

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

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

    results := [][]int{}
    leftToRight := true

    queue := []*TreeNode{root}

    for len(queue) > 0 {
        levelSize := len(queue)
        level := []int{}

        for i := 0; i < levelSize; i++ {
            node := queue[0]
            queue = queue[1:]
            level = append(level, node.Val)

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

        if !leftToRight {
            for i, j := 0, len(level)-1; i < j; i, j = i+1, j-1 {
                level[i], level[j] = level[j], level[i]
            }
        }

        results = append(results, level)
        leftToRight = !leftToRight
    }

    // Print the results slice
    // Your code here
}

Hint

Use fmt.Println(results) to print the final zigzag traversal.