#103

Medium

auto_awesomeBinary-tree traversal and state tracking

LeetCode Problem Workspace

Binary Tree Zigzag Level Order Traversal

Traverse a binary tree in zigzag level order, alternating directions at each depth using BFS and state tracking techniques efficiently.

tree breadth first search binary tree

Problem Statement

Given the root of a binary tree, return the zigzag level order traversal of its nodes' values. Each level alternates between left-to-right and right-to-left order, requiring careful state tracking of traversal direction. You must ensure that nodes are grouped correctly per depth and maintain consistent alternation across all levels. The solution should handle empty trees and trees with a single node without errors.

For example, given a binary tree like root = [3,9,20,null,null,15,7], the expected output is [[3],[20,9],[15,7]]. Your implementation must efficiently manage the queue for BFS while reversing node order at appropriate levels. Constraints include a maximum of 2000 nodes and node values between -100 and 100, emphasizing correct traversal without unnecessary memory overhead.

Examples

Example 1

Input: root = [3,9,20,null,null,15,7]

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

Example details omitted.

Example 2

Input: root = [1]

Output: [[1]]

Example details omitted.

Example 3

Input: root = []

Output: []

Example details omitted.

Constraints

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

Solution Approach

Breadth-First Search with Level Queue

Use a queue to perform a breadth-first traversal of the binary tree. Start by enqueuing the root node and iterate through each level, recording node values in a temporary list. Track the level number or use a boolean flag to decide whether to reverse the order of values for that level. Append the processed list to the final result. This approach ensures linear traversal and properly handles alternating directions without modifying the tree structure.

Using Double-Ended Queue for Efficient Reversals

Replace the simple queue with a deque to allow appending values from both ends depending on traversal direction. For left-to-right levels, append normally; for right-to-left levels, append to the front of the deque. This eliminates the need for explicit list reversal at each level, reducing overhead. After processing each level, convert the deque to a list before adding it to the result. This technique optimizes both time and space while maintaining clear directional state tracking.

Recursive Depth-First Approach with Level Tracking

Implement a DFS traversal while passing the current level index in the recursion. For each node, append its value to a corresponding sublist in the result. Reverse the sublist for odd-numbered levels to achieve the zigzag effect. This approach leverages recursion to implicitly manage the node order per level but requires careful handling of the result structure and recursion depth to prevent stack overflow on large trees.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity is O(n) because every node is visited exactly once in either BFS or DFS traversal, and reversal operations per level are bounded by node counts. Space complexity is O(n) as well, due to the queue or recursion stack and storing the result list containing all node values. Both time and space scale linearly with the total number of nodes in the tree, which is consistent with the constraints.

What Interviewers Usually Probe

Do you maintain the current level direction while traversing nodes to ensure proper zigzag order?
Can you optimize the reversal step to avoid creating new lists unnecessarily at each level?
Will you handle edge cases such as empty trees or single-node trees correctly?

Common Pitfalls or Variants

Common pitfalls

Forgetting to reverse the node values at every alternate level, resulting in standard level order output instead of zigzag.
Using a standard queue without managing insertion direction, which forces costly list reversals each time and increases overhead.
Incorrectly indexing levels during recursion or BFS, causing misplacement of node values and breaking the zigzag pattern.

Follow-up variants

Binary Tree Level Order Traversal without zigzag reversal, focusing solely on left-to-right BFS grouping per level.
Spiral Order Traversal of a binary tree with two stacks, an alternative DFS-based method to achieve zigzag order.
Bottom-Up Zigzag Level Order Traversal where the traversal starts from leaves to root, requiring reversed collection after BFS.

FAQ

What is the correct way to track level direction in Binary Tree Zigzag Level Order Traversal?

Use a boolean flag or level index to determine whether to append node values left-to-right or right-to-left. This ensures that each level alternates correctly and that the zigzag pattern is maintained across all tree depths.

Can I use DFS instead of BFS for this zigzag traversal problem?

Yes, DFS can work by passing the current level in recursion and appending values to sublists, reversing sublists at odd levels. Care is needed for recursion depth and result initialization.

How do I handle an empty tree or a single-node tree?

Return an empty list for an empty tree and a nested list containing the single node value for single-node trees. This prevents runtime errors and ensures output consistency.

Is using a deque more efficient than a list reversal for zigzag levels?

Yes, a deque allows O(1) insertion at both ends, avoiding full list reversal per level, which reduces overhead while maintaining correct zigzag order.

What are common mistakes to avoid in Binary Tree Zigzag Level Order Traversal?

Avoid skipping level tracking, forgetting to reverse odd levels, and mishandling queue or recursion order, as each can break the zigzag pattern and produce incorrect output.

terminal

Solution

Solution 1: BFS

To implement zigzag level order traversal, we need to add a flag `left` on the basis of level order traversal. This flag is used to mark the order of the node values in the current level. If `left` is `true`, the node values of the current level are stored in the result array `ans` from left to right. If `left` is `false`, the node values of the current level are stored in the result array `ans` from right to left.

# 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]]:
        ans = []
        if root is None:
            return ans
        q = deque([root])
        ans = []
        left = 1
        while q:
            t = []
            for _ in range(len(q)):
                node = q.popleft()
                t.append(node.val)
                if node.left:
                    q.append(node.left)
                if node.right:
                    q.append(node.right)
            ans.append(t if left else t[::-1])
            left ^= 1
        return ans

Continue Practicing

#102 binary tree level order traversal #104 maximum depth of binary tree #101 symmetric tree