Binary Tree Zigzag Level Order Traversal

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

Example(s)

Example 1:

Tree:
    1
   / \
  2   3
Output: [[1],[3,2]]

Example 2:

Tree:
      8
     / \
    2   29
         / \
        3   9
Output: [[8],[29,2],[3,9]]

Solution

JavaScript Solution

JavaScript Zigzag Level Order Traversal Solution

/**
* 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)
* }
*/

/**
* Perform zigzag level order traversal of a binary tree
* @param {TreeNode} root - Root of the binary tree
* @return {number[][]} - Zigzag level order traversal result
*/
function zigzagLevelOrder(root) {
if (!root) return [];

const result = [];
const queue = [root];
let leftToRight = true;

while (queue.length) {
  const levelSize = queue.length;
  const currentLevel = [];
  
  for (let i = 0; i < levelSize; i++) {
    const node = queue.shift();
    currentLevel.push(node.val);
    if (node.left) queue.push(node.left);
    if (node.right) queue.push(node.right);
  }
  
  if (!leftToRight) {
    currentLevel.reverse();
  }
  
  result.push(currentLevel);
  leftToRight = !leftToRight;
}

return result;
}

// Test case 1: [1,2,3]
const tree1 = new TreeNode(1);
tree1.left = new TreeNode(2);
tree1.right = new TreeNode(3);

// Test case 2: [8,2,29,null,null,3,9]
const tree2 = new TreeNode(8);
tree2.left = new TreeNode(2);
tree2.right = new TreeNode(29);
tree2.right.left = new TreeNode(3);
tree2.right.right = new TreeNode(9);

// Test cases
console.log(zigzagLevelOrder(tree1)); // [[1],[3,2]]
console.log(zigzagLevelOrder(tree2)); // [[8],[29,2],[3,9]]
console.log(zigzagLevelOrder(null)); // []

Output:

Click "Run Code" to execute the code and see the results.

Python Solution

Python Zigzag Level Order Traversal Solution

from typing import Optional, List
from collections import deque

# 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

def zigzag_level_order(root: Optional[TreeNode]) -> List[List[int]]:
  """
  Perform zigzag level order traversal of a binary tree
  
  Args:
      root: Root of the binary tree
      
  Returns:
      List[List[int]]: Zigzag level order traversal result
  """
  if not root:
      return []
  
  result = []
  queue = deque([root])
  left_to_right = True
  
  while queue:
      level_size = len(queue)
      current_level = []
      
      for _ in range(level_size):
          node = queue.popleft()
          current_level.append(node.val)
          if node.left:
              queue.append(node.left)
          if node.right:
              queue.append(node.right)
      
      if not left_to_right:
          current_level.reverse()
      
      result.append(current_level)
      left_to_right = not left_to_right
  
  return result

# Test case 1: [1,2,3]
tree1 = TreeNode(1)
tree1.left = TreeNode(2)
tree1.right = TreeNode(3)

# Test case 2: [8,2,29,null,null,3,9]
tree2 = TreeNode(1)
tree2.left = TreeNode(2)
tree2.right = TreeNode(29)
tree2.right.left = TreeNode(3)
tree2.right.right = TreeNode(9)

# Test cases
print(zigzag_level_order(tree1))  # [[1],[3,2]]
print(zigzag_level_order(tree2))  # [[8],[29,2],[3,9]]
print(zigzag_level_order(None))  # []

Loading Python runtime...

Output:

Click "Run Code" to execute the code and see the results.

Complexity

• Time Complexity: O(n) - Where n is the number of nodes in the tree
• Space Complexity: O(w) - Where w is the maximum width of the tree

Approach

The solution uses a breadth-first search (BFS) approach:

1. Level-by-level traversal using a queue
2. Track level size to process all nodes at each level
3. Toggle direction between left-to-right and right-to-left
4. Reverse level when going right-to-left
5. Return array of arrays representing each level

Key Insights

• Breadth-first search ensures level-by-level traversal
• Queue data structure efficiently processes nodes in order
• Direction toggle alternates between left-to-right and right-to-left per level
• Edge cases include empty tree, single-node tree, and single-level trees
• O(n) time is optimal as all nodes must be visited