Binary Tree Zigzag Level Order Traversal
Medium · Trees · Tree · Breadth-First Search · Binary Tree
Problem
Given the root of a binary tree, return its values level by level, alternating direction: the root level is read left to right, the next level right to left, the one after left to right again, and so on.
Return one list per level; an empty tree gives an empty list.
Trees are written in level order: values row by row, left to right, with null for a missing child. [3,9,20,null,null,15,7] is a root 3 with children 9 and 20, where 20 has children 15 and 7. TreeNode, from_level and to_level are provided.
Examples
Input: root = [1,2,3,4,5,6,7] Output: [[1],[3,2],[4,5,6,7]]
The middle level is read right to left; the first and third are not.
Input: root = [4,9,null,2,8] Output: [[4],[9],[2,8]]
The one-node middle level looks the same in either direction, and the third level is read left to right again.
Input: root = [] Output: []
Nothing to traverse.
Constraints
- The tree has between 0 and 2000 nodes
- -100 <= Node.val <= 100
Approaches
- Baseline: one walk from the root per level — time O(n · h), space O(h)
Follow-up
Could you produce each row already in the right order without reversing? Use a deque per level: append values at the back on left-to-right levels and at the front on right-to-left levels. The total work is the same O(n).
Related problems
Start free on Cariara · Coding problems · System design studio
