Binary Tree Zigzag Level Order Traversal
Read a binary tree one level at a time and flip direction as you go: the top level reads left to right, the next one right to left, then left to right again. Return the values as one list per level, and an empty list for an empty tree. The tree comes in as a level-order list in which a missing child is null. Limits: 0 <= number of nodes <= 100000, and every value is between -100 and 100. Think about: what do you need to remember from one level to the next? Example: tree [5, 2, 9, 1, 4, 7, 11] level 0, left to right: 5 level 1, right to left: 9, 2 level 2, left to right: 1, 4, 7, 11 Return [[5],[9,2],[1,4,7,11]].
This is level-order traversal with a twist: read the top level left to right, the next one right to left, and keep flipping. Interviewers love it because it shows whether you can bolt one small rule onto a plain level-by-level walk without breaking it. Watch the order you queue children in: get it wrong and every level after the first flip comes out scrambled. Expect up to 100,000 nodes with values from -100 to 100.
Examples
You write
zigzag_level_order(root: Optional[TreeNode])
Example 1
- Input
- [5,2,9,1,4,7,11]
- returns
- [[5],[9,2],[1,4,7,11]]
Example 2
- Input
- []
- returns
- []
Save this for your laptop
The editor and Run need a bigger screen. The link opens Binary Tree Zigzag Level Order Traversal ready to code. It is free, and the editor needs no account.
The pattern behind it
Trees
I reach for it when
- Each node has children, and the answer depends on the subtrees.
- The statement says depth, height, ancestor or path.
Say this before you type. Say what a call returns for an empty tree, and what it returns for a node.
All 22 Trees problemsBFS & DFS
I reach for it when
- You walk a grid, a graph or a tree and visit each cell once.
- The word shortest appears and every step costs the same.
Say this before you type. Say why breadth or depth fits, and exactly when a cell counts as visited.
All 52 BFS & DFS problems
Meet Coco
Coco is an AI study partner, not a person. She listens while you explain your code, asks what a line does and never hands you the fix. Sign in free to type with Coco, up to a daily limit, and to talk with her for one hour. After that, talking comes with the $79 pack. Anyone can open the editor and run their code.