Binary Tree Zigzag Level Order Traversal Medium 0 attempts
LeetCode ↗

Binary Tree Zigzag Level Order Traversal

Medium TreeBinary TreeDFS LeetCode

You're given the root of a binary tree. Return its node values grouped level by level, but alternate the reading direction of each level — left-to-right, then right-to-left, and so on down the tree.

Input Format
Implement zigzagLevelOrder(root). Inputs below show JavaScript function arguments; there is no stdin parsing. Trees use level-order arrays with null for missing children. The editor passes nodes with val, left, and right properties; [] becomes null.
Output Format
Return the result described in the statement.

Sample Input and Output

Example 1 · Run Sample

Input
root = [3,9,20,null,null,15,7]
Output
[[3],[20,9],[15,7]]

Example 2

Input
root = []
Output
[]
Constraints
  • 0 <= number of nodes <= 2000
  • -100 <= Node.val <= 100
Test Cases (2)
Case 1
Args: [[3,9,20,null,null,15,7]] Expected: [[3],[20,9],[15,7]]
Case 2
Args: [[]] Expected: []
Topics
TreeBinary TreeDFS

BFS with Direction Flag

javascript
function zigzagLevelOrder(root) {
  if (!root) return [];
  const result = [], q = [root];
  let leftToRight = true;
  let head = 0;
  while (head < q.length) {
    const level = [], size = q.length - head;
    for (let i = 0; i < size; i++) {
      const node = q[head++];
      level.push(node.val);
      if (node.left) q.push(node.left);
      if (node.right) q.push(node.right);
    }
    result.push(leftToRight ? level : level.reverse());
    leftToRight = !leftToRight;
  }
  return result;
}

Time: O(n) | Space: O(n)

Saved in this browser only. Private to you.

JavaScript