103. Binary Tree Zigzag Level Order Traversal
mediumReturn 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 Sam K., 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
root = [3,9,20,null,null,15,7][[3],[20,9],[15,7]]Example 2
root = [1][[1]]Example 3
root = [][]Solve it now
Free. No sign-up. Python and JavaScript run instantly in your browser.
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
More Trees practice problems
- 94. Binary Tree Inorder Traversal
- 98. Validate Binary Search Tree
- 100. Same Tree
- 101. Symmetric Tree
- 102. Binary Tree Level Order Traversal
- 104. Maximum Depth of Binary Tree
- 105. Construct Binary Tree from Preorder and Inorder Traversal
- 108. Convert Sorted Array to Binary Search Tree