Binary Tree Zigzag Traversal
Binary Tree Zigzag Traversal
Given a binary tree, perform a zigzag level-order traversal: traverse the first level left to right, the second level right to left, the third level left to right, and so on, alternating direction at each level. Your solve(...) function receives these inputs directly as ready-made arguments — no input reading or parsing needed. Just compute and return the answer. Example: level-order [3 9 20 -1 -1 15 7] → "3 20 9 15 7" (level 1: left→right gives 3; level 2: right→left gives 20 9; level 3: left→right gives 15 7)
Input format — only if your code reads from stdin
Input format (stdin): - First line: integer n (size of the level-order array) - Second line: n space-separated integers, where -1 represents a null node Output: the zigzag traversal values, all on a single line, space-separated.
Approach
BFS level by level. Track a direction flag (toggling each level). For even levels, read left-to-right; for odd levels, read right-to-left (or collect and reverse). A deque makes this efficient — append to front or back based on direction.
Input
Output
- •
0 ≤ n ≤ 2000, -100 ≤ node values ≤ 100
More Trees problems
Browse all coding problems →Press Run to test your custom input, or Submit to judge against all test cases.
Sign in to continue
Create a free account to run code, submit solutions and track progress.
- Free forever — no credit card
- 10+ languages with live execution
- Points, streaks & leaderboards