103. Binary Tree Zigzag Level Order Traversal - Detailed Explanation

Problem Statement

Given the root of a binary tree, return the zigzag level order traversal of its nodes' values. This means that for the first level you traverse from left to right, for the second level from right to left, and you continue alternating for subsequent levels.

Example 1

• Input: root = [3, 9, 20, null, null, 15, 7]
• Output: [[3], [20, 9], [15, 7]]
• Explanation:
  • Level 1: Only node 3 → [3]
  • Level 2: Nodes 9 and 20; since it is the second level, traverse right-to-left → [20, 9]
  • Level 3: Nodes 15 and 7; traverse left-to-right again → [15, 7]

Example 2

• Input: root = [1]
• Output: [[1]]
• Explanation:
  • Only one level with the single node 1.

Example 3

• Input: root = []
• Output: []
• Explanation:
  • The tree is empty, so the output is an empty list.

Constraints:

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

Hints

1. Think about using a level order traversal (BFS) with a queue to process the tree level by level.
2. To achieve the zigzag pattern, consider reversing the list of node values on every alternate level or using a data structure that allows adding elements at the beginning when needed.

Approaches

Approach 1: DFS (Recursive) with Level Tracking

Explanation

• Idea: Use depth-first search (DFS) to traverse the tree recursively while keeping track of the current level.
• Steps:

  1. Define a helper function that accepts a node and its level.

  2. If the current level does not have a list in your result structure, create one.

  3. Depending on whether the current level is even or odd, either append the node’s value at the end or insert it at the beginning of the corresponding list.

  4. Recursively traverse the left and right children while incrementing the level.

• Visual Example:
  For the tree [3, 9, 20, null, null, 15, 7]:
  • Start at level 0 with node 3.
  • Go to level 1: process node 9 and node 20. For level 1 (odd), insert values at the beginning so that the order becomes [20, 9].
  • Continue recursively for the next level.

Complexity Analysis

• Time Complexity: O(n), where n is the number of nodes (each node is visited once).

• Space Complexity: O(n) due to the recursion stack (in the worst case of a skewed tree) and storage for the output.

Python Code (DFS Recursive)