Binary Tree Zigzag Level Order Traversal

---

Binary Tree Zigzag Level Order Traversal: 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:

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

---

Try this Problem on your own or check similar problems:

1. Binary Tree Level Order Traversal
2. Binary Tree Level Order Traversal II
3. Average of Levels in Binary Tree

Solution:

Java

public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
    if(root == null) return List.of();

    List<List<Integer>> result = new ArrayList<>();
    Queue<TreeNode> q = new LinkedList<>();
    boolean isReversed = false;

    q.add(root);
    while(!q.isEmpty()){
        int size = q.size();
        List<Integer> level = new ArrayList<>();
        while(size-->0){
            TreeNode node = q.poll();
            if(node.left != null){
                q.add(node.left);
            }
            if(node.right != null){
                q.add(node.right);
            }
            level.add(node.val);
        }
        if(isReversed) Collections.reverse(level);
        isReversed = !isReversed;
        result.add(level);
    }

    return result;
}

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) {
  if (!root) {
    return [];
  }

  const result = [];
  const queue = [];
  let isReversed = false;

  queue.push(root);

  while (queue.length > 0) {
    const level = [];
    const size = queue.length;

    for (let i = 0; i < size; i++) {
      const node = queue.shift();

      if (node.left) {
        queue.push(node.left);
      }
      if (node.right) {
        queue.push(node.right);
      }

      level.push(node.val);
    }

    if (isReversed) {
      level.reverse();
    }

    result.push(level);
    isReversed = !isReversed;
  }

  return result;
};

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
class Solution:
    def zigzagLevelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        if not root:
            return []

        result = []
        queue = deque([root])
        isReversed = False

        while queue:
            level = []
            size = len(queue)

            for _ in range(size):
                node = queue.popleft()

                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)

                level.append(node.val)

            if isReversed:
                level.reverse()

            result.append(level)
            isReversed = not isReversed

        return result

C++

/**
 * 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) {
        if (!root) {
            return {};
        }

        std::vector<std::vector<int>> result;
        std::queue<TreeNode*> q;
        bool isReversed = false;

        q.push(root);

        while (!q.empty()) {
            int size = q.size();
            std::vector<int> level;

            for (int i = 0; i < size; i++) {
                TreeNode* node = q.front();
                q.pop();

                if (node->left) {
                    q.push(node->left);
                }
                if (node->right) {
                    q.push(node->right);
                }

                level.push_back(node->val);
            }

            if (isReversed) {
                std::reverse(level.begin(), level.end());
            }

            result.push_back(level);
            isReversed = !isReversed;
        }

        return result;
    }
};

---

Time/Space Complexity:

• Time Complexity: O(n)
• Space Complexity: O(n)

---

Explanation:

We use the implementation from Binary Tree Level Order Traversal only this time with a flag isReversed which if set would reverse the current level. Since isReversed will be true (since it's alternating between true and false for every level change) only for even levels (2nd, 4th... ) we will only reverse those levels. We return the list of levels as our result. Space and time complexity remain unchanged.