{x}
blog image

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

Solution Explanation: Binary Tree Zigzag Level Order Traversal

This problem requires traversing a binary tree level by level, but with an alternating left-to-right and right-to-left order for each level. This is known as a zigzag traversal. The most efficient approach uses Breadth-First Search (BFS).

Approach: BFS with Direction Toggle

  1. Initialization: We start with a queue q containing the root node and an empty result list ans. A boolean variable left is initialized to true, indicating that the first level should be traversed from left to right.

  2. Level-by-Level Traversal: The main loop continues as long as the queue q is not empty. In each iteration, we process one level of the tree.

  3. Processing a Level: A temporary list t stores the node values of the current level. We iterate through the current size of the queue. For each node, we:

    • Add the node's value to t.
    • Enqueue the node's left and right children (if they exist) to q.

  4. Zigzag Ordering: After processing a level, we check the value of left.

    • If left is true, the values in t are already in the correct left-to-right order; we append t directly to ans.
    • If left is false, we reverse t before appending it to ans to achieve the right-to-left order.

  5. Direction Toggle: We then toggle the value of left (left = !left) to switch the direction for the next level.

  6. Return Result: Finally, we return the ans list containing the zigzag level order traversal.

Time and Space Complexity Analysis

  • Time Complexity: The algorithm visits each node in the tree exactly once. Therefore, the time complexity is O(N), where N is the number of nodes in the binary tree.

  • Space Complexity: In the worst case (a complete binary tree), the queue q can hold up to O(N/2) ≈ O(N) nodes at any given time. The ans list also stores at most N values. Therefore, the space complexity is O(N).

Code Examples (Python, Java, C++, Go, TypeScript, Rust, JavaScript)

The code examples in various programming languages provided in the original response accurately implement this BFS-based approach. The core logic remains consistent across all languages, differing only in syntax and data structure implementations (e.g., queue, deque, vector). Each example includes comments to enhance readability and understanding.