# LeetCode 103: Binary Tree Zigzag Level Order Traversal ## Problem Restatement We are given the `root` of a binary tree. We need to return the values level by level. The first level is read from left to right, the second level from right to left, the third level from left to right, and so on. The official problem asks for the zigzag level order traversal of a binary tree's node values. For this tree: ```text 3 / \ 9 20 / \ 15 7 ``` The normal level order traversal would be: ```python [[3], [9, 20], [15, 7]] ``` The zigzag level order traversal is: ```python [[3], [20, 9], [15, 7]] ``` The second level is reversed. ## Input and Output | Item | Meaning | |---|---| | Input | `root`, the root node of a binary tree | | Output | A list of lists of integers | | First level | Left to right | | Second level | Right to left | | Later levels | Keep alternating direction | | Empty tree | Return `[]` | LeetCode gives the `TreeNode` class: ```python class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right ``` The function shape is: ```python class Solution: def zigzagLevelOrder(self, root: Optional[TreeNode]) -> list[list[int]]: ... ``` ## Examples Consider this tree: ```text 3 / \ 9 20 / \ 15 7 ``` Level `0` is read left to right: ```python [3] ``` Level `1` is read right to left: ```python [20, 9] ``` Level `2` is read left to right: ```python [15, 7] ``` So the answer is: ```python [[3], [20, 9], [15, 7]] ``` For a single-node tree: ```text 1 ``` The answer is: ```python [[1]] ``` For an empty tree, the answer is: ```python [] ``` ## First Thought: Use Normal Level Order Traversal The problem still asks for values grouped by level. That means breadth-first search is the natural traversal method. The only difference from normal level order traversal is the order of values inside each level. We can still visit nodes left to right with a queue. After collecting one level, we decide whether to keep it as is or reverse it. ## Key Insight The traversal order and output order can be handled separately. The queue should always process nodes in normal left-to-right order: ```text node.left before node.right ``` This keeps the next level organized correctly. Then, for each level, use a boolean flag: ```python left_to_right = True ``` If `left_to_right` is true, append the level values normally. If it is false, append the reversed level values. After each level, flip the flag. ## Algorithm If `root` is `None`, return `[]`. Otherwise: 1. Create a queue containing `root`. 2. Create an empty answer list. 3. Set `left_to_right = True`. 4. While the queue has nodes: 1. Create an empty list for the current level. 2. Read the current queue size. 3. Process exactly that many nodes. 4. Append each node value to the current level list. 5. Add the left child if it exists. 6. Add the right child if it exists. 7. If the direction is right to left, reverse the level list. 8. Append the level list to the answer. 9. Flip the direction. 5. Return the answer. ## Correctness The queue begins with the root, so the first processed group is level `0`. At the start of each outer loop, the queue contains exactly the nodes of the current level in left-to-right order. We store the queue size before processing the level, so nodes added during this loop are saved for the next level. For every node, the algorithm adds the left child before the right child. Therefore, the next level is also stored in left-to-right order in the queue. The algorithm then uses `left_to_right` to choose the output order for the current level. On even-numbered levels, it keeps the collected values in left-to-right order. On odd-numbered levels, it reverses them, producing right-to-left order. After each level, the flag is flipped. Therefore, the output direction alternates on every level. So every level is included exactly once, every node value appears in the correct level, and the direction alternates as required. ## Complexity | Metric | Value | Why | |---|---|---| | Time | `O(n)` | Each node is processed once | | Space | `O(n)` | The queue and output can store up to `n` values | Here, `n` is the number of nodes in the tree. Reversing a level costs time proportional to that level's size. Across the whole tree, all reversals together still cost `O(n)`. ## Implementation ```python from collections import deque from typing import Optional # Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: def zigzagLevelOrder(self, root: Optional[TreeNode]) -> list[list[int]]: if root is None: return [] ans = [] q = deque([root]) left_to_right = True while q: level = [] for _ in range(len(q)): node = q.popleft() level.append(node.val) if node.left is not None: q.append(node.left) if node.right is not None: q.append(node.right) if not left_to_right: level.reverse() ans.append(level) left_to_right = not left_to_right return ans ``` ## Code Explanation We first handle the empty tree: ```python if root is None: return [] ``` Then we create the queue: ```python q = deque([root]) ``` The direction flag starts as `True` because the first level is read left to right: ```python left_to_right = True ``` The outer loop processes one level at a time: ```python while q: ``` For each level, we collect values in normal left-to-right order: ```python level = [] ``` This loop runs only for the nodes already in the current level: ```python for _ in range(len(q)): ``` Each node is removed from the front of the queue: ```python node = q.popleft() ``` Then its value is stored: ```python level.append(node.val) ``` The children are added from left to right: ```python if node.left is not None: q.append(node.left) if node.right is not None: q.append(node.right) ``` If the current level should be read right to left, we reverse the collected values: ```python if not left_to_right: level.reverse() ``` Then we store the level and flip the direction: ```python ans.append(level) left_to_right = not left_to_right ``` Finally: ```python return ans ``` ## Testing ```python from collections import deque from typing import Optional class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right class Solution: def zigzagLevelOrder(self, root: Optional[TreeNode]) -> list[list[int]]: if root is None: return [] ans = [] q = deque([root]) left_to_right = True while q: level = [] for _ in range(len(q)): node = q.popleft() level.append(node.val) if node.left is not None: q.append(node.left) if node.right is not None: q.append(node.right) if not left_to_right: level.reverse() ans.append(level) left_to_right = not left_to_right return ans def run_tests(): s = Solution() root1 = TreeNode( 3, TreeNode(9), TreeNode(20, TreeNode(15), TreeNode(7)), ) assert s.zigzagLevelOrder(root1) == [[3], [20, 9], [15, 7]] root2 = TreeNode(1) assert s.zigzagLevelOrder(root2) == [[1]] root3 = None assert s.zigzagLevelOrder(root3) == [] root4 = TreeNode( 1, TreeNode(2, TreeNode(4), TreeNode(5)), TreeNode(3, TreeNode(6), TreeNode(7)), ) assert s.zigzagLevelOrder(root4) == [[1], [3, 2], [4, 5, 6, 7]] root5 = TreeNode( 1, TreeNode(2, TreeNode(3, TreeNode(4))), None, ) assert s.zigzagLevelOrder(root5) == [[1], [2], [3], [4]] print("all tests passed") run_tests() ``` Test meaning: | Test | Why | |---|---| | `[3,9,20,null,null,15,7]` | Standard example | | Single node | Minimum non-empty tree | | Empty tree | Confirms empty output | | Complete tree | Confirms alternating order across full levels | | Left-skewed tree | Confirms one-node levels still work |