Return the values of a binary tree level by level, but alternate the direction. The first level goes left to right, the next right to left, and so on.
DSA Animator › DSA Revision › Tree › Binary Tree Zigzag Level Order Traversal
Remember: do not change the order you visit nodes, only where you write them. The index n minus 1 minus k reverses a level for free. The video solves Binary Tree Zigzag Level Order Traversal (LeetCode 103, Medium) with the BFS Level Order pattern from the Tree topic, and you can replay every step in the interactive Binary Tree Zigzag Level Order Traversal animation.
Return the values of a binary tree level by level, but alternate the direction. The first level goes left to right, the next right to left, and so on.
For the tree 3, 9, 20, 15, 7, the answer is 3, then 20 and 9, then 15 and 7. The second level is reversed, because it reads from right to left.
One way is to run a normal level order traversal, and then reverse every second level at the end. That is fine, but it touches some levels twice. We can place each value in its correct slot directly.
Run a normal breadth first search, one level per round. Keep a flag that says whether the current level goes left to right. For each level, create a list of exactly the level size. The k-th node popped goes to index k when going left to right, or to index size minus 1 minus k when going right to left. Flip the flag after every level.
Level 0 holds only 3, and it goes left to right. Pushing its children gives 9 and 20 for the next level. Level 1 goes right to left, so 9, popped first, goes into the last slot. 20, popped second, goes into the first slot, so the level reads 20, 9. Their children 15 and 7 form level 2. Level 2 goes left to right again, so it stays 15, 7. The answer is 3, then 20, 9, then 15, 7.
In code, use a queue and a boolean, left to right, that starts as true. For each level, make an array of size n. When you poll the k-th node, choose the index k or n minus 1 minus k based on the flag. Push the children in the normal order, and flip the flag after the level. Each node is handled once, so it is O of n time.
Remember: do not change the order you visit nodes, only where you write them. The index n minus 1 minus k reverses a level for free.