Given the root of a binary tree, return the zigzag level order traversal of its nodes’ values. (i.e., from left to right, then right to left for the next level and alternate between).

Examples

Example 1:

Input: root = [3,9,20,null,null,15,7]
Output: [[3],[20,9],[15,7]]
Explanation:
Level 0: [3] (left to right)
Level 1: [20,9] (right to left)
Level 2: [15,7] (left to right)

Example 2:

Input: root = [1]
Output: [[1]]

Example 3:

Input: root = []
Output: []

Constraints

  • The number of nodes in the tree is in the range [0, 2000].
  • -100 <= Node.val <= 100

Thinking Process

  1. BFS Structure: Maintains level-by-level traversal
  • Trees have no cycles — recursion is natural.
  • Combine results from left and right subtrees at each node.
  • Base case is usually null; height drives stack space.
Graph BFS layers S a b t BFS: expand by layers (queue)

Common Approaches

Typical techniques for this pattern:

Approach Time Space Notes
Queue BFS O(n) O(n) Shortest path in unweighted graphs
Multi-source BFS O(n) O(n) Start from all sources simultaneously
0-1 BFS / deque O(n) O(n) Weights 0 or 1
Level-order BFS (this problem) O(n) O(w) Process by depth/layer

Solution

Solution: BFS with Deque and Direction Toggle

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        vector<vector<int>> rtn;
        if(root == nullptr) return rtn;

        deque<TreeNode*> queue;
        queue.push_back(root);
        bool leftToRight = true;

        while(!queue.empty()) {
            int size = queue.size();
            vector<int> level;
            for(int i = 0; i < size; i++) {
                TreeNode* curr = queue.front();
                queue.pop_front();
                if(leftToRight) {
                    level.push_back(curr->val);
                } else {
                    level.insert(level.begin(), curr->val);
                }
                if(curr->left) queue.push_back(curr->left);
                if(curr->right) queue.push_back(curr->right);
            }
            rtn.push_back(level);
            leftToRight = !leftToRight;
        }
        return rtn;
    }
};

Solution Explanation

Approach: Level-order BFS (this problem)

Key idea: 1. BFS Structure: Maintains level-by-level traversal

How the code works:

  1. BFS Structure: Maintains level-by-level traversal
    • Trees have no cycles — recursion is natural.
    • Combine results from left and right subtrees at each node.
    • Base case is usually null; height drives stack space.

Walkthrough — input root = [3,9,20,null,null,15,7], expected output [[3],[20,9],[15,7]]:

Level 0: [3] (left to right) Level 1: [20,9] (right to left) Level 2: [15,7] (left to right)

Algorithm Explanation:

  1. Initialize (Lines 4-6):
    • Create empty result vector
    • Return empty result if root is null
    • Initialize deque with root node
    • Set leftToRight = true for first level
  2. Level Processing (Lines 8-25):
    • For each level:
      • Get current level size (number of nodes at this level)
      • Create empty level vector
      • Process each node at current level:
        • Remove node from front of deque
        • Add value based on direction:
          • If leftToRight: append to end of level vector
          • If rightToLeft: insert at beginning of level vector
        • Add children: Always add left child first, then right child to back of deque
      • Add completed level to result
      • Toggle direction: leftToRight = !leftToRight
  3. Return (Line 26): Return the zigzag level order traversal

Why This Works:

  • Deque for BFS: deque allows efficient removal from front and insertion at back
  • Direction Toggle: Alternates between left-to-right and right-to-left
  • Insertion Strategy:
    • Left-to-right: push_back() - natural order
    • Right-to-left: insert(begin()) - reverse order
  • Children Order: Always add left then right to maintain level structure

Example Walkthrough:

For root = [3,9,20,null,null,15,7]:

Tree structure:
    3
   / \
  9   20
     /  \
    15   7

Level 0 (leftToRight = true):
  Process: [3]
  Add: level = [3]
  Children: [9, 20]
  Result: [[3]]

Level 1 (leftToRight = false):
  Process: [9, 20]
  Add: level.insert(9) → [9], then level.insert(20) → [20, 9]
  Children: [15, 7]
  Result: [[3], [20, 9]]

Level 2 (leftToRight = true):
  Process: [15, 7]
  Add: level.push_back(15) → [15], then level.push_back(7) → [15, 7]
  Children: []
  Result: [[3], [20, 9], [15, 7]]

Complexity Analysis:

Implementation Notes

  1. Deque vs Queue: Deque allows efficient insertion at both ends
  2. Insert Performance: insert(begin()) is O(n) per level, but acceptable for this problem
  3. Direction Flag: Simple boolean toggle is cleaner than using level number % 2
  4. Null Check: Always check for null root before processing

Common Mistakes

  • Skipping edge cases (empty input, single element, boundaries).
  • Off-by-one errors in loops and index ranges.
  • Forgetting to handle the case when no valid answer exists.

Key Takeaways

  1. BFS Structure: Maintains level-by-level traversal
  2. Direction Toggle: Simple boolean flag to alternate direction
  3. Insertion Strategy: Choose insertion method based on direction
  4. Children Order: Always process left then right to maintain level structure

References

Template Reference