Skip to main content

103. Binary Tree Zigzag Level Order Traversal

medium

Return a level-by-level traversal that alternates direction — left-to-right on odd levels, right-to-left on even ones. A tiny twist on plain BFS that trips up anyone who reverses the queue instead of the output.

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

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]]

Example 3

Input
root = []
Output
[]

Solve it now

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

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

BFS with per-level batching is the foundation. The only addition is a direction flag that flips each level.

Hint 2

Don't reverse the queue — that breaks the next level's ordering. Reverse only the level list before appending to result.

Hint 3

Or use a deque for the level: appendLeft when going right-to-left, append when going left-to-right.

Solution approach

Reveal approach

Standard level-order BFS with an alternating flag. Initialize queue with root (early-return empty if root is null), leftToRight = true, result = []. Loop while queue non-empty: snapshot levelSize, build a level array of that many elements by popping the queue. For each popped node, place its value at index i if leftToRight else (levelSize - 1 - i), and enqueue its non-null children in left,right order. Append level to result. Flip leftToRight. Return result. The placement-by-index avoids any reversal of the queue. O(n) time, O(width) extra space.

Complexity

Time
O(n)
Space
O(n)

Related patterns

  • tree-bfs
  • queue

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Microsoft
  • Bloomberg
  • LinkedIn

Practice these live with InterviewChamp.AI

Drill Binary Tree Zigzag Level Order Traversal and Trees problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →