Binary Tree Zigzag Level Order Traversal

1. Define the problem

Binary Tree Zigzag Level Order Traversal

Return the values of the tree level by level, but change direction each time: the first level reads left to right , the second level reads right to left , the third left to right again, and so on. The tree arrives as a level-order array such as [3, 9, 20, null, null, 15, 7], with null for a missing child. Your function builds the tree and returns an array of arrays, one inner array per level. Collect each level normally, then reverse the odd-numbered levels before adding them to the answer. The walk itself never changes direction.

Constraints

The number of nodes is between 0 and 2000
-100 ≤ node value ≤ 100
Input is a level-order array with null for a missing child
Return an array of arrays; an empty tree returns an empty array

Example

Inputvalues = [3, 9, 20, null, null, 15, 7]

Output[[3], [20, 9], [15, 7]]

Explanation Level 0 is [3] and reads left to right. Level 1 holds 9 then 20, and because it is an odd level it is reversed to [20, 9]. Level 2 holds 15 then 7 and reads left to right again.

2. Know the words first

In plain terms

Level order: Reading a tree one whole level at a time, from the root downwards, instead of following one branch to the bottom first.
Zigzag: Alternating the reading direction level by level, so the path of values snakes from side to side down the tree.
Array of arrays: A list whose items are themselves lists. Here the outer list holds one entry per level, and each entry holds that level’s values.

3. Visualize the solution

One cell per value in the final output, in the order the values are emitted

out 0—

out 1—

out 2—

out 3—

out 4—

Statusinit

The tree is built and the current level holds only the root.

What happens in this step

values = [3, 9, 20, null, null, 15, 7]

level = [3]
levelIndex = 0
out = []

Step 1 of 6

Steps to visualize

Each cell is a slot in the flattened answer, filled in the order the values come out.
The nodes of a level are always collected left to right.
Only when writing a level into the answer do the odd levels get reversed.
The highlighted range shows the cells one level just produced.

4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

One cell per value in the final output, in the order the values are emitted

out 0—

out 1—

out 2—

out 3—

out 4—

Statusinit

The tree is built and the current level holds only the root.

What happens in this step

values = [3, 9, 20, null, null, 15, 7]

level = [3]
levelIndex = 0
out = []

Step 1 of 6

5. Solution

Solution

solution.tsTypeScript

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

  function buildTree(list) {
    if (list.length === 0 || list[0] === null) {
      return null;
    }

    const root = new Node(list[0]);
    const queue = [root];
    let i = 1;

    while (i < list.length && queue.length > 0) {
      const node = queue.shift();

      if (list[i] !== null && list[i] !== undefined) {
        node.left = new Node(list[i]);
        queue.push(node.left);
      }

      i += 1;

      if (list[i] !== null && list[i] !== undefined) {
        node.right = new Node(list[i]);
        queue.push(node.right);
      }

      i += 1;
    }

    return root;
  }

  const root = buildTree(values);
  const out = [];

  if (root === null) {
    return out;
  }

  let level = [root];
  let levelIndex = 0;

  while (level.length > 0) {
    const rowValues = level.map(function (node) {
      return node.val;
    });

    if (levelIndex % 2 === 0) {
      out.push(rowValues);
    } else {
      out.push(rowValues.reverse());
    }

    const next = [];

    for (const node of level) {
      if (node.left !== null) {
        next.push(node.left);
      }

      if (node.right !== null) {
        next.push(node.right);
      }
    }

    level = next;
    levelIndex += 1;
  }

  return out;
}

Time: O(n)
Space: O(w)

6. Test cases

Test cases

Input	Expected	Covers
`values = [3, 9, 20, null, null, 15, 7]`	`[[3], [20, 9], [15, 7]]`	example from the docstring
`values = [1]`	`[[1]]`	one node, one level
`values = []`	`[]`	empty tree, no levels at all
`values = [1, 2, 3, 4, null, null, 5]`	`[[1], [3, 2], [4, 5]]`	a level with missing children still reverses correctly
`values = [1, 2, 3, 4, 5, 6, 7]`	`[[1], [3, 2], [4, 5, 6, 7]]`	a complete tree with three levels
`values = [1, null, 2, null, 3]`	`[[1], [2], [3]]`	one node per level, so reversing changes nothing

Binary Tree Zigzag Level Order Traversal