Skip to main content

71. Binary Tree Zigzag Level Order Traversal

mediumAsked at Plaid

Return the zigzag level order traversal of a tree. Plaid asks this as a BFS variant — exactly the shape they use when alternating left-to-right vs right-to-left iteration over partitioned ledger shards.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Source citations

Public interview reports confirming this problem appears in Plaid loops.

  • Glassdoor (2025)— Plaid SWE II OA.
  • LeetCode Discuss (2026)— Plaid BFS 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 = []
Output
[]

Approaches

1. Level order then reverse alternates

Standard BFS, then reverse every other output row.

Time
O(n)
Space
O(n)
function zigzagLevelOrder(root) {
  if (!root) return [];
  const out = [];
  let level = [root];
  let rev = false;
  while (level.length) {
    const vals = [];
    const next = [];
    for (const n of level) {
      vals.push(n.val);
      if (n.left) next.push(n.left);
      if (n.right) next.push(n.right);
    }
    out.push(rev ? vals.reverse() : vals);
    level = next;
    rev = !rev;
  }
  return out;
}

Tradeoff: Two passes per level (build then maybe reverse). Acceptable.

2. Deque with direction toggle

Use a deque; push children to front or back depending on direction.

Time
O(n)
Space
O(w)
// Slightly more involved; same asymptotic. Mention for completeness.

Tradeoff: Avoids the explicit reverse but adds complexity in queue ops.

Plaid-specific tips

Plaid grades this on clarity. The reverse-on-odd-level approach is the readable industrial default. Bonus signal: discuss when the deque variant matters — only if reversing a level is a measurable cost, e.g., when levels are huge.

Common mistakes

  • Reversing the BFS queue itself — affects the order of children pushed to the next level, which is wrong.
  • Toggling direction before pushing instead of after.
  • Forgetting the empty-root early return.

Follow-up questions

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

  • Vertical order (LC 314).
  • Boundary traversal.
  • Spiral order on a grid.

Solve it now

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

Output

Press Run or Cmd+Enter to execute

FAQ

Why reverse the output, not the traversal?

Reversing the queue would push children in the wrong order, breaking subsequent levels. Reversing only the output preserves the standard BFS order.

Is reverse() O(n)?

Yes, but it's O(level width), and we do it once per level. Total work stays O(n).

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →