Zigzag Level Order Traversal of a Binary Tree in Go
This is part 4of the series — working with Binary Trees in Go. In this article, I will show how to perform zigzag level order traversal of a binary tree in Go.
- Part 1 Binary Tree Traversals in Go (access it here)
- Part 2 Binary Tree Traversals in Go — using iteration (access it here)
- Part 3 Level order Traversal of Binary Trees in Go (access it here)
- Part4 Zigzag Level Order Traversal of a Binary Tree in Go (this article)
- Part 5 Right side View of a Binary Tree in Go
- Part 6 Binary Tree Serialization in Go
Given the root of a binary tree, return the zigzag level order traversal of its nodes’ values (i.e. for level zero the nodes’ values should be returned from left to right, for level one the nodes’ values should be returned from right to left and for the next level the nodes’ values should be again from left to right and so on)
As an example, consider the tree shown in the picture below. The zigzag level order output for this tree is [[50], [30, 40], [10, 20, 80]].

Initial Thoughts
The problem is very similar to level order traversal with a twist. I can first perform level order traversal to obtain the output and then reverse the nodes’ values in every alternate level in the output array. I will show how to code this solution in Method 1. In Method 2, I will also show how to avoid this extra reverse operation so as obtain the zigzag output directly.
Method 1: Perform Level Order Traversal Followed by Reversal Operation
I have shown how to perform level order traversal in my previous post and hence I will skip those details here. With the level ordering logic figured out, the code becomes really simple as shown in the following gist.
Method 2: Avoid Reversal Operation
As part of the level order traversal inner loop as shown in the previous post, we collect the nodes’ values that belong to the same level in a slice i.e., we always take nodes’ values in left to right order. Instead of doing that, we can use a flag that determines whether to store the nodes’ values forward or backward in the array. And the flag can be toggled at every iteration of the outer loop which effectively changes the ordering from “left to right” to “right to left” and vice versa. The following code shows the details.