Binary Tree Zigzag Level Order Traversal
Signals to notice
Brute force first
Level order traversal then reverse every other level — but requires post-processing. That instinct is useful because it follows the prompt literally, but it usually keeps revisiting work the problem is begging you to organize.
The key insight
BFS with a flag that alternates each level. On even levels, append normally. On odd levels, prepend (or reverse the level array). Instead of recomputing the world every time, you preserve just enough context to let the next decision become obvious.
What must stay true
The BFS queue always processes nodes left-to-right. The zigzag effect comes from how you ADD the results to the level array — prepend on odd levels to reverse the apparent order. As long as that statement keeps holding, you can trust the steps built on top of it.
Easy way to go wrong
Trying to change the queue processing order — that's complex. Easier to always process left-to-right and just reverse the output for alternate levels. Most mistakes here are not about syntax; they come from losing track of what your state, pointer, or structure is supposed to mean.