Rabi Siddique
147 words
1 minutes
Zig Zag Traversal in Golang

Zigzag level order traversal is an algorithm that traverses a binary tree in a zigzag pattern: left to right on one level, then right to left on the next level, and so on. Here’s my solution for the problem:


package DSA

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

func zigzagLevelOrder(root *TreeNode) [][]int {
	if root == nil {
		return [][]int{}
	}

	queue := []*TreeNode{root}
	output := [][]int{}
	leftToRight := true

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

		for i := 0; i < levelSize; i++ {
			currentNode := queue[0]
			queue = queue[1:]

			if leftToRight {
				level = append(level, currentNode.Val)
			} else {
				level = append([]int{currentNode.Val}, level...)
			}

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

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

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

	return output
}

Zig Zag Traversal in Golang
https://rabisiddique.com/posts/zig-zag-in-go/
Author
Rabi Siddique
Published at
2024-02-13