# Binary Tree Zigzag Level Order Traversal
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/binary-tree-zigzag-level-order-traversal)
Canonical: https://scaleengineer.com/dsa/problems/binary-tree-zigzag-level-order-traversal
**Algorithms:** [Breadth-First Search](https://scaleengineer.com/algorithms/breadth-first-search)
**Data structures:** Tree, Binary Tree
**Companies:** [Adobe](https://scaleengineer.com/companies/adobe), [Bloomberg](https://scaleengineer.com/companies/bloomberg), [ByteDance](https://scaleengineer.com/companies/bytedance), [Flipkart](https://scaleengineer.com/companies/flipkart), [Intuit](https://scaleengineer.com/companies/intuit), [LinkedIn](https://scaleengineer.com/companies/linkedin), [Meta](https://scaleengineer.com/companies/meta), [Microsoft](https://scaleengineer.com/companies/microsoft), [Nutanix](https://scaleengineer.com/companies/nutanix), [Oracle](https://scaleengineer.com/companies/oracle), [ServiceNow](https://scaleengineer.com/companies/servicenow), [TikTok](https://scaleengineer.com/companies/tiktok), [Walmart Labs](https://scaleengineer.com/companies/walmart-labs), [Yandex](https://scaleengineer.com/companies/yandex), [eBay](https://scaleengineer.com/companies/ebay), [Citadel](https://scaleengineer.com/companies/citadel), [Sigmoid](https://scaleengineer.com/companies/sigmoid)
---
## Problem
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).

**Example 1:**

![](https://assets.glich.co/dsa/binary-tree-zigzag-level-order-traversal/image0.jpg) 

**Input:** root = [3,9,20,null,null,15,7]
**Output:** [[3],[20,9],[15,7]]

**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`

# Approaches
## BFS with List Reversal
This approach builds upon the standard BFS level-order traversal. We traverse the tree level by level using a queue. For each level, we store the node values in a temporary list. A flag or a level counter is used to determine the traversal direction. If the current level needs to be traversed from right to left, we simply reverse the temporary list before adding it to our final result.
**Time:** O(N) · **Space:** O(W)
**Pros:** Easy to understand as it's a small modification of the standard level-order traversal.; The logic is straightforward and simple to implement.
**Cons:** The explicit reversal step (`Collections.reverse`) adds a performance overhead compared to more optimized solutions, as it requires an extra pass over the nodes of every other level.
### Explanation
This method is a direct extension of the standard Breadth-First Search (BFS) algorithm for level-order traversal. The main idea is to perform a regular level-order traversal and collect all nodes at a given level. After a level is fully processed, we decide whether to add it to the result as is (for left-to-right levels) or to reverse it first (for right-to-left levels). A boolean flag, toggled at the end of each level's processing, keeps track of the required order.

```java
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) {
            return result;
        }

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        boolean leftToRight = true;

        while (!queue.isEmpty()) {
            int levelSize = queue.size();
            List<Integer> currentLevel = new ArrayList<>(levelSize);
            for (int i = 0; i < levelSize; i++) {
                TreeNode node = queue.poll();
                currentLevel.add(node.val);
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }

            if (!leftToRight) {
                Collections.reverse(currentLevel);
            }
            result.add(currentLevel);
            leftToRight = !leftToRight;
        }
        return result;
    }
}
```
### Algorithm
- Initialize an empty list `result` to store the final zigzag traversal.
- If the `root` is null, return the empty `result`.
- Initialize a queue (e.g., `LinkedList`) and add the `root` to it.
- Initialize a boolean flag `leftToRight` to `true`.
- While the queue is not empty:
  - Get the number of nodes in the current level, `levelSize`.
  - Create a new list `currentLevel` to store the values for this level.
  - Loop `levelSize` times:
    - Dequeue a node.
    - Add its value to `currentLevel`.
    - Enqueue its left child if it's not null.
    - Enqueue its right child if it's not null.
  - If `leftToRight` is `false`, reverse the `currentLevel` list.
  - Add `currentLevel` to the `result` list.
  - Flip the `leftToRight` flag for the next level.
- Return the `result`.

## Depth-First Search (DFS)
This approach uses recursion (DFS) to traverse the tree. We maintain the current level's depth as we traverse. The core idea is to add nodes to the correct level's list in the final result. For even-numbered levels (0, 2, ...), we append the node's value to the end of the list. For odd-numbered levels (1, 3, ...), we insert the node's value at the beginning of the list. This prepending action effectively reverses the order of nodes for odd levels.
**Time:** O(N) · **Space:** O(H)
**Pros:** Elegant recursive solution.; Can be more space-efficient than BFS for balanced trees (O(log N) vs O(N) for queue space).
**Cons:** Less intuitive for a level-order problem, which is naturally solved with BFS.; Can lead to a `StackOverflowError` for very deep, unbalanced trees.; Requires using a `LinkedList` for each level to maintain O(1) insertion at the beginning; using an `ArrayList` would degrade performance.
### Explanation
Instead of the iterative BFS, we can solve this problem using a recursive Depth-First Search. We perform a preorder traversal and pass the current depth or level as an argument to the recursive function. The `result` list will store lists of nodes for each level. When we visit a node at a certain `level`, we check if a list for this level already exists in our `result`. If not, we create one. To achieve the zigzag effect, we check if the current level is even or odd. For even levels, we append the node's value to the end of the list. For odd levels, we prepend the value to the beginning of the list. Using a `LinkedList` for each level's list makes the prepending operation efficient (O(1)).

```java
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        dfs(root, 0, result);
        return result;
    }

    private void dfs(TreeNode node, int level, List<List<Integer>> result) {
        if (node == null) {
            return;
        }

        // If we are at a new level, create a new list for it.
        // Using LinkedList for efficient prepending (addFirst).
        if (level >= result.size()) {
            result.add(new LinkedList<>());
        }

        List<Integer> levelList = result.get(level);
        if (level % 2 == 0) {
            // Left to right
            levelList.add(node.val);
        } else {
            // Right to left
            // Add at the beginning for odd levels
            ((LinkedList<Integer>) levelList).addFirst(node.val);
        }

        dfs(node.left, level + 1, result);
        dfs(node.right, level + 1, result);
    }
}
```
### Algorithm
- Initialize an empty list `result`.
- Define a recursive helper function, `dfs(node, level, result)`.
- Call the helper function with the `root` and `level = 0`.
- Inside `dfs(node, level, result)`:
  - If `node` is null, return.
  - If `level` is equal to the current size of `result`, it means we are visiting this level for the first time. Add a new `LinkedList` to `result`.
  - Get the list for the current level: `levelList = result.get(level)`.
  - If `level` is even, add `node.val` to the end of `levelList`.
  - If `level` is odd, add `node.val` to the beginning of `levelList`.
  - Recursively call `dfs(node.left, level + 1, result)`.
  - Recursively call `dfs(node.right, level + 1, result)`.
- Return the `result`.

## BFS with a Deque
This is a highly efficient and elegant approach that uses a single double-ended queue (deque). Instead of reversing lists, we control the order of processing nodes and adding their children to the deque. We use a flag to alternate between left-to-right and right-to-left traversal for each level.
**Time:** O(N) · **Space:** O(W)
**Pros:** Most efficient approach in terms of constant factors as it avoids explicit list reversal.; The logic of adding/removing from both ends of the deque is clean and directly builds the zigzag order.; Uses a single data structure to manage the traversal.
**Cons:** The logic can be slightly more complex to grasp initially compared to the simple reversal method.
### Explanation
This optimized BFS approach uses a double-ended queue (deque) to avoid the costly list reversal step. The key is to alter how we process nodes and enqueue their children based on the traversal direction of the current level.

- For a **left-to-right** level, we poll nodes from the **front** of the deque and add their children (left then right) to the **back**.
- For a **right-to-left** level, we poll nodes from the **back** of the deque and add their children (right then left) to the **front**.

This way, the nodes for the next level are always placed in the deque in the correct order for their subsequent traversal, eliminating the need for any post-processing like reversal.

```java
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
import java.util.Deque;

class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) {
            return result;
        }

        Deque<TreeNode> deque = new LinkedList<>();
        deque.offerFirst(root);
        boolean leftToRight = true;

        while (!deque.isEmpty()) {
            int levelSize = deque.size();
            List<Integer> currentLevel = new ArrayList<>(levelSize);
            
            for (int i = 0; i < levelSize; i++) {
                if (leftToRight) {
                    TreeNode node = deque.pollFirst();
                    currentLevel.add(node.val);
                    if (node.left != null) {
                        deque.offerLast(node.left);
                    }
                    if (node.right != null) {
                        deque.offerLast(node.right);
                    }
                } else {
                    TreeNode node = deque.pollLast();
                    currentLevel.add(node.val);
                    if (node.right != null) {
                        deque.offerFirst(node.right);
                    }
                    if (node.left != null) {
                        deque.offerFirst(node.left);
                    }
                }
            }
            result.add(currentLevel);
            leftToRight = !leftToRight;
        }
        return result;
    }
}
```
### Algorithm
- Initialize an empty list `result` and a deque (e.g., `LinkedList`).
- If `root` is null, return the empty `result`.
- Add the `root` to the deque.
- Initialize a boolean flag `leftToRight` to `true`.
- While the deque is not empty:
  - Get the number of nodes in the current level, `levelSize`.
  - Create a new list `currentLevel` to store values.
  - Loop `levelSize` times:
    - If `leftToRight` is `true`:
      - Poll a node from the front of the deque (`pollFirst`).
      - Add its value to `currentLevel`.
      - Add its left child (if not null) to the back of the deque (`offerLast`).
      - Add its right child (if not null) to the back of the deque (`offerLast`).
    - If `leftToRight` is `false`:
      - Poll a node from the back of the deque (`pollLast`).
      - Add its value to `currentLevel`.
      - Add its right child (if not null) to the front of the deque (`offerFirst`).
      - Add its left child (if not null) to the front of the deque (`offerFirst`).
  - Add `currentLevel` to the `result`.
  - Flip the `leftToRight` flag.
- Return `result`.

# Solutions
### Java

```java
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { public List < List < Integer >> zigzagLevelOrder ( TreeNode root ) { List < List < Integer >> ans = new ArrayList <>(); if ( root == null ) { return ans ; } Deque < TreeNode > q = new ArrayDeque <>(); q . offer ( root ); boolean left = true ; while (! q . isEmpty ()) { List < Integer > t = new ArrayList <>(); for ( int n = q . size (); n > 0 ; -- n ) { TreeNode node = q . poll (); t . add ( node . val ); if ( node . left != null ) { q . offer ( node . left ); } if ( node . right != null ) { q . offer ( node . right ); } } if (! left ) { Collections . reverse ( t ); } ans . add ( t ); left = ! left ; } return ans ; } } ////// public class Binary_Tree_Zigzag_Level_Order_Traversal { /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ // count as level marker class Solution { public List < List < Integer >> zigzagLevelOrder ( TreeNode root ) { List < List < Integer >> result = new ArrayList <>(); if ( root == null ) { return result ; } boolean isLeftToRight = true ; Queue < TreeNode > q = new LinkedList <>(); q . offer ( root ); int currentLevelCount = 1 ; int nextLevelCount = 0 ; List < Integer > one = new ArrayList <>(); while (! q . isEmpty ()) { TreeNode current = q . poll (); currentLevelCount --; if ( isLeftToRight ) { one . add ( current . val ); } else { one . add ( 0 , current . val ); } if ( current . left != null ) { q . offer ( current . left ); nextLevelCount ++; } if ( current . right != null ) { q . offer ( current . right ); nextLevelCount ++; } if ( currentLevelCount == 0 ) { currentLevelCount = nextLevelCount ; nextLevelCount = 0 ; result . add ( one ); one = new ArrayList <>(); isLeftToRight = ! isLeftToRight ; } } return result ; } } public class Solution_nullAsMarker { public List < List < Integer >> zigzagLevelOrder ( TreeNode root ) { List < List < Integer >> list = new ArrayList < List < Integer >>(); if ( root == null ) { return list ; } Queue < TreeNode > q = new LinkedList <>(); q . offer ( root ); q . offer ( null ); // @note: use null as marker for end of level boolean direction = true ; // true: left=>right, false: right=>left List < Integer > oneLevel = new ArrayList <>(); while (! q . isEmpty ()) { TreeNode current = q . poll (); if ( current == null ) { List < Integer > copy = new ArrayList <>( oneLevel ); list . add ( copy ); // clean after one level recorded oneLevel . clear (); // @memorize: this api direction = ! direction ; // @note:@memorize: if stack is now empty then DO NOT add null, or else infinite looping // sk.offer(null); // add marker if (! q . isEmpty ()) { q . offer ( null ); // add marker } continue ; } if ( direction ) { oneLevel . add ( current . val ); } else { oneLevel . add ( 0 , current . val ); } // @note:@memorize: since using null as marker, then must avoid adding null when children are null // sk.offer(current.left); // sk.offer(current.right); if ( current . left != null ) { q . offer ( current . left ); } if ( current . right != null ) { q . offer ( current . right ); } } return list ; } } }
```

### JavaScript

```javascript
/** * Definition for a binary tree node. * function TreeNode(val, left, right) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } */ /** * @param {TreeNode} root * @return {number[][]} */ var zigzagLevelOrder =
  function (root) {
    const ans = [];
    if (!root) {
      return ans;
    }
    const q = [root];
    let left = 1;
    while (q.length) {
      const t = [];
      for (let n = q.length; n; --n) {
        const node = q.shift();
        t.push(node.val);
        if (node.left) {
          q.push(node.left);
        }
        if (node.right) {
          q.push(node.right);
        }
      }
      if (!left) {
        t.reverse();
      }
      ans.push(t);
      left ^= 1;
    }
    return ans;
  };

```

### CPP

```cpp
/** * 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 >> ans ; if ( ! root ) return ans ; queue < TreeNode *> q { { root } }; int left = 1 ; while ( ! q . empty ()) { vector < int > t ; for ( int n = q . size (); n ; -- n ) { auto node = q . front (); q . pop (); t . emplace_back ( node -> val ); if ( node -> left ) q . push ( node -> left ); if ( node -> right ) q . push ( node -> right ); } if ( ! left ) reverse ( t . begin (), t . end ()); ans . emplace_back ( t ); left ^= 1 ; } return ans ; } };
```

### Python

```python
# 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 ''' can also use list.insert() >>> my_list = [2, 3, 4] >>> my_list.insert(0, 1) # Insert 1 at the head of the list >>> print(my_list) # Output: [1, 2, 3, 4] >>> a = deque([]) >>> a deque([]) >>> a.append(1) >>> a.append(2) >>> a.append(3) >>> a deque([1, 2, 3]) >>> >>> a.append(0, 555) Traceback (most recent call last): File "<stdin>", line 1, in <module> TypeError: deque.append() takes exactly one argument (2 given) >>> a.insert(0, 555) >>> a deque([555, 1, 2, 3]) ''' from collections import deque class Solution : def zigzagLevelOrder ( self , root : Optional [ TreeNode ]) -> List [ List [ int ]]: ans = [] if root is None : return ans q = deque ([ root ]) ans = [] left = True while q : t = [] for _ in range ( len ( q )): node = q . popleft () t . append ( node . val ) if node . left : q . append ( node . left ) if node . right : q . append ( node . right ) ans . append ( t if left else t [:: - 1 ]) left = ( not left ) return ans ############ # Definition for a binary tree node. # class TreeNode(object): # def __init__(self, x): # self.val = x # self.left = None # self.right = None from collections import deque class Solution ( object ): def zigzagLevelOrder ( self , root ): """ :type root: TreeNode :rtype: List[List[int]] """ stack = deque ([ root ]) ans = [] odd = True while stack : level = [] for k in range ( 0 , len ( stack )): top = stack . popleft () if top is None : continue level . append ( top . val ) stack . append ( top . left ) stack . append ( top . right ) if level : if odd : ans . append ( level ) else : ans . append ( level [:: - 1 ]) odd = not odd return ans ############ # 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 ]]: ans = [] if root is None : return ans q = deque ([ root ]) ans = [] left = 1 while q : t = [] for _ in range ( len ( q )): node = q . popleft () t . append ( node . val ) if node . left : q . append ( node . left ) if node . right : q . append ( node . right ) ans . append ( t if left else t [:: - 1 ]) left ^= 1 return ans
```