Binary Tree Zigzag Level Order Traversal

Given the root of a binary tree, implement a function that performs a level order traversal but alternates the direction of traversal for each level. This is a common tree traversal variation used in various algorithms and data structure manipulations, helping to process tree nodes in a more structured, snake-like pattern.

Problem Description

The goal is to traverse a binary tree level by level, but with a twist:

• Level 0 (root): Traverse from left to right.
• Level 1: Traverse from right to left.
• Level 2: Traverse from left to right.
• Level 3: Traverse from right to left.
• ...and so on, alternating direction for each subsequent level.

The function should return a list of lists, where each inner list represents a level of the tree and contains the values of the nodes at that level, ordered according to the zigzag traversal.

Key Requirements:

• The traversal must start with left-to-right for the root level.
• The direction must alternate for each subsequent level.
• The output should be a list of lists, preserving the order of levels.

Edge Cases to Consider:

• An empty tree (root is null).
• A tree with only a root node.
• A tree that is skewed (e.g., a linked list).

Examples

Example 1:

Input:
      3
     / \
    9  20
      /  \
     15   7

Output:
[[3], [20, 9], [15, 7]]

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

Example 2:

Input:
      1
     / \
    2   3
   / \
  4   5

Output:
[[1], [3, 2], [4, 5]]

Explanation:
Level 0 (left-to-right): [1]
Level 1 (right-to-left): [3, 2]
Level 2 (left-to-right): [4, 5]

Example 3:

Input:
      1

Output:
[[1]]

Explanation:
Level 0 (left-to-right): [1]

Constraints

• The number of nodes in the tree is between 0 and 2000.
• Node values are integers between -100 and 100.
• The tree structure is valid.
• Performance: The solution should ideally run in O(N) time complexity, where N is the number of nodes, and O(W) space complexity, where W is the maximum width of the tree (for storing nodes at a level).

Notes

• You will be given the root of a binary tree. Assume a standard TreeNode structure with value, left, and right properties.
• Consider using a queue for the level order traversal part. The zigzag logic will likely involve managing the order of elements added to the result list for each level.
• A boolean flag or a counter can be used to keep track of the current traversal direction.