PPractick

The problem

A visualisation of a family tree animates the generations in a snake pattern: the first row left to right, the next row right to left, then left to right again, like a spiral. It's level-order BFS, except every other level is reversed. Keep a direction flag that flips after each level, and fill each level's list from the front or from the back depending on the flag.

Example: [3, 9, 20, null, null, 15, 7] → [[3], [20, 9], [15, 7]].

Function signature

vector<vector<int>> zigzagLevelOrder(TreeNode* root);

Test cases

Input (level order)	Output	Explanation
[3, 9, 20, null, null, 15, 7]	[[3], [20, 9], [15, 7]]
[1, 2, 3, 4, 5, 6, 7]	[[1], [3, 2], [4, 5, 6, 7]]
[1, 2, 3, 4, null, null, 5]	[[1], [3, 2], [4, 5]]
[1]	[[1]]
[]	[]

(Confirm: level 0 is left to right, level 1 right to left, and so on.)

How interviewers phrase it

• "Given the root of a binary tree, return the zigzag level order traversal of its nodes' values" (LeetCode 103; GeeksforGeeks calls it "spiral" order, and sometimes starts right to left, so check which direction comes first).

Clarifying questions to ask

1. Which direction does the first level use? (Left to right here.)
2. One list per level, or flat? (One per level.)
3. Can the tree be empty?

Follow-ups to expect

1. "Why not reverse the children's push order?"
2. "Two-stack alternative?"
3. "Deque alternative?"
4. "Why is writing into a pre-sized vector O(1)?"
5. "Complexity?"

Related questions

• Vertical Order Traversal Medium
• Top View of BT Medium
• Bottom view of BT Medium
• Right/Left View of Binary Tree Medium
• Maximum Width of BT Medium
• Pre, Post, Inorder in one traversal Easy

All 474 dsa interview questions

DSA mock interviews · System design interview questions · Free mock interview practice · Browse interviewers · Sign in