Zigzag Level Order Traversal of a Binary Tree in Javascript (Recursive)

In my last 2 posts I talked about level order traversal, once with a recursive solution and once with an iterative solution. In this post I’ll be covering a very similar problem: Leetcode problem #103 Binary Tree Zigzag Level Order Traversal. The problem may seem intimidating and complicated at first, but if you understand the recursive solution to the straightforward level order traversal, it’s actually VERY similar.

In the simple level order traversal problem

• We initiated an empty result array and then created a helper function to call recursively.
• The helper function accepted 2 arguments: the current node and the current level. Each level number corresponded with the index position of that level subarray in the result array.
• Accordingly, with the initial call (the first level), we called the function with our root node, and 0 for the level parameter.
• We then added each node to a subarray at the index of its level within the result array.
• Then, each time we called the function recursively for child nodes, we incremented the level.

So that gives us a good old fashioned level order traversal, but how do we accomplish the zig zag in this version? If you think about what the zig zag is, it means we are alternating traversing each level from left to right and from right to left. So for our first level, we are traversing left to right (even though there is just 1 node), then for our second level we traverse right to left, third level left to right, fourth level right to left etc.

Another way to look at this, since we are alternating with each zig zag, is that we traverse odd-leveled rows left to right, and even leveled rows right to left.

So for our result array, how do we reflect right to left traversal? A simple way to do this is to check the row level, and if it is even, add the element on to the front of its result array. If the level is odd, push it on to the end. It’s that simple!

Here it is in code with comments walking through each step:

Hope this helps!