63. Binary Tree Zigzag Level Order Traversal

Q: Reverse or deque — which is faster?

Same asymptotic. Reverse is more idiomatic in JS; deque is more natural in C++/Python.

Q: Does the order of children push matter?

Always push left then right. Reversing only affects the output VALUE order, not the traversal order.

mediumAsked at Datadog

Return a binary tree's level-order traversal but alternate left-to-right and right-to-left per level. Datadog uses this BFS variant to test that you can compose direction-flipping on top of the level-batch primitive.

By Alex Chen, Founder, InterviewChamp.AI · Last verified 2026-05-20

Source citations

Public interview reports confirming this problem appears in Datadog loops.

Glassdoor (2026-Q1)— Datadog onsite — BFS direction-flip variant.

Problem

Given the root of a binary tree, return the zigzag level order traversal of its nodes' values. (i.e., from left to right, then right to left for the next level and alternate between).

Constraints

The number of nodes in the tree is in the range [0, 2000].
-100 <= Node.val <= 100

Examples

Example 1

Input

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

Output

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

Example 2

Input

root = [1]

Output

[[1]]

Approaches

1. BFS + reverse alternate levels

Standard BFS; reverse every other level's array at the end.

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

function zigzagLevelOrder(root) {
  if (!root) return [];
  const out = [];
  let q = [root];
  let leftToRight = true;
  while (q.length) {
    const level = [];
    const next = [];
    for (const n of q) {
      level.push(n.val);
      if (n.left) next.push(n.left);
      if (n.right) next.push(n.right);
    }
    if (!leftToRight) level.reverse();
    out.push(level);
    leftToRight = !leftToRight;
    q = next;
  }
  return out;
}

Tradeoff: Simple and clean. O(n) reverse cost is dominated by O(n) overall.

2. BFS with deque + direction flag (optimal-feel)

Use a deque. On left-to-right levels, push to back; on right-to-left, push to front.

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

// Use a deque per level: shift/push depending on direction. Slightly less idiomatic in JS.

Tradeoff: Equivalent O(n). Skips the reverse but uses deque operations. Pick whichever you prefer — Datadog accepts both.

Datadog-specific tips

Datadog grades on composability: zigzag = level-order + reverse alternate. Articulate this — don't reinvent the BFS. The follow-up is usually 'now do this on a tree streamed in chunks' — show that the level-batch primitive handles each chunk-boundary independently.

Common mistakes

Reversing the wrong levels (off-by-one on which direction starts) — root level should be left-to-right.
Reversing in place inside the for-loop instead of after — bugs.
Forgetting to flip the direction flag — produces single-direction output.

Follow-up questions

An interviewer at Datadog may pivot to one of these next:

Binary Tree Level Order Traversal (LC 102) — base case.
Vertical Order Traversal (LC 987) — different axis.
Datadog-style: alternating-direction page rendering of a metric tree.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

Reverse or deque — which is faster?

Same asymptotic. Reverse is more idiomatic in JS; deque is more natural in C++/Python.

Does the order of children push matter?

Always push left then right. Reversing only affects the output VALUE order, not the traversal order.

Practice these live with InterviewChamp.AI

Drill Binary Tree Zigzag Level Order Traversal and other Datadog interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →