Good morning! Here's our prompt for today.

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    1
2   / \
3  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    1
2   / \
3  2  3
4    /  \
5   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:

1    4
2   / \
3  3  12
4    /  \
5   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:

1function Node(val) {
2  this.val = val;
3  this.left = null;
4  this.right = null;
5}

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)

Try to solve this here or in Interactive Mode.

How do I practice this challenge?

xxxxxxxxxx

  assertIsFunction(zigZagTraversal, '`zigZagTraversal` should be a function');

var assert = require('assert');

​

function zigZagTraversal(root) {

  // implement this method

  return root;

}

​

function Node(val) {

  this.val = val;

  this.left = null;

  this.right = null;

}

​

// Regular binary trees

var tree1 = new Node(4);

tree1.left = new Node(1);

tree1.right = new Node(3);

​

var tree2 = new Node(5);

tree2.left = new Node(10);

tree2.left.left = new Node(17);

tree2.left.right = new Node(3);

tree2.right = new Node(8);

​

// Binary search trees

var tree3 = new Node(6);

tree3.left = new Node(3);

​

var tree4 = new Node(5);

Here's a video of us explaining the solution.

To change the speed of the video or see it in full screen, click the icons to the right of the progress bar.

Here's our guided, illustrated walk-through.

How do I use this guide?