Balanced tree example
Input
build_tree_from_list([1,2,3,4,5,6,7])
Output
[[1], [3, 2], [4, 5, 6, 7]]
Level 0: [1] (left->right). Level 1: [2,3] reversed -> [3,2]. Level 2: [4,5,6,7] (left->right).
Full lesson preview
Compute zigzag level order traversal
Return the zigzag (spiral) level-order traversal of a binary tree.
Python practice13 minTrees & Binary TreesIntermediateLast updated March 29, 2026
Problem statement
Given the root of a binary tree, return its zigzag level order traversal as a list of lists of node values. The first level is left-to-right, the next is right-to-left, and so on, alternating for each level. If the tree is empty, return an empty list.
Task
Implement a function to traverse a binary tree level-by-level, alternating direction at each level.
Examples
Input format
A binary tree root (TreeNode) constructed with build_tree_from_list([...]).
Output format
A list of lists of integers representing zigzag level order traversal.
Constraints
Nodes values are integers. Number of nodes can be up to a few thousand; aim for O(n) time and O(width) extra space.
Samples
Sample 1
Input
build_tree_from_list([3,9,20,None,None,15,7])
Output
[[3], [20, 9], [15, 7]]
Root 3, next level [9,20] reversed, final level [15,7].