Here is the interview question prompt, presented for reference.

Here's a fun one: can you write a method to return the nodes of a binary tree in a zig zag level order?

It should return a multi-dimensional array of arrays, with each child array being a level of the tree. That's a mouthful, so here's an example:

    1
   / \
  2  3

This basic binary tree would result in [[1], [3, 2]]. Here's why: at the first level, we went left-right, but there's only one node (1), so it is appended to an array by itself. Then, at the second level, we'll zig-zag. Instead of [left, right], we'll go [right, left], and thus we get [3, 2].

    1
   / \
  2  3
    /  \
   4    5

would result in [[1], [3, 2], [4, 5].

The order should be zig zag. Again, you'll start by moving left to right. At the level below, you'll move from right to left, and so on.

Take this binary tree as another example:

    4
   / \
  3  12
    /  \
   8    14

We'll start at 4 and since there's only one node, we'll "move left-to-right", and just add [4].

Then we would move on to the second level, and move right-to-left, adding [12, 3] in the process. Finally, we switch again, and move left-to-right, getting [8, 14].

Could you define the method zigZagTraversal(root)? As usual, you may assume the following definition for all nodes, including the root:

function Node(val) {
  this.val = val;
  this.left = null;
  this.right = null;
}

Constraints

• Number of vertices in the tree <= 100000
• The values of the vertices will be between -1000000000 and 1000000000
• Expected time complexity : O(n)
• Expected space complexity : O(n)

You can see the full challenge with visuals at this link.