Binary Tree Zigzag Level Order Traversal

medium ~15 min

TreeNode(val, left=None, right=None) is in the starter. Keep it.

Implement zigzag_level_order(root) -> list[list[int]]: the node values grouped by depth, root level first, but the reading direction flips on every level. The root's level (level 0) reads left to right, level 1 right to left, level 2 left to right again, and so on. An empty tree gives [].

#          5
#        /   \
#       3     8
#      / \     \
#     1   4     9
#              /
#             7
zigzag_level_order(root)   # [[5], [8, 3], [1, 4, 9], [7]]

The tree 5; 3 and 8; 1, 4 and 9; then 7, with levels 0 and 2 read left to right and levels 1 and 3 read right to left

zigzag_level_order(TreeNode(2, None, TreeNode(6)))   # [[2], [6]]
zigzag_level_order(None)                             # []

Up to 131,071 nodes; values are integers between -10^6 and 10^6.
The direction depends on the level's depth, not on how many nodes it has.

⭐ Bonus: a speed test on a 131,071-node tree earns a star in O(n) time.

Show hint

Do a normal level-by-level walk with a queue, always adding children left then right. Build each level's list in that order, then reverse it on the odd levels before you add it to the answer.

Topic: Binary trees. Recursive return values (height, best path), BFS by level, BST invariants.

Read the visual guide