Binary Tree Zigzag Level Order Traversal Solution for Microsoft

Company: Microsoft · Difficulty: Medium · Topics: 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. (i.e., from left to right, then right to left for the next level and alternate between).

Examples

Example 1:

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

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

Explanation:

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

Example 2:

Input: root = [1]

Output: [[1]]

Explanation:

Only one level with one node.

Example 3:

Input: root = []

Output: []

Explanation:

Empty tree, no nodes to traverse.

Example 4:

Input: root = [1,2,3,4,5,6,7]

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

Explanation:

• Level 0: [1] (left to right)
• Level 1: [3,2] (right to left)
• Level 2: [4,5,6,7] (left to right)

Intuition

The key insight is to use a breadth-first search (BFS) approach with level tracking. We need to:

1. Use a queue to process nodes level by level

2. Keep track of the current level

3. Reverse the order of nodes at odd levels (1, 3, 5, ...)

4. Maintain the original order at even levels (0, 2, 4, ...)

This can be achieved by either:

• Using a flag to track level direction
• Using a stack for odd levels and queue for even levels
• Collecting all nodes at each level and reversing odd levels

Approach

Approach 1: BFS with Level Tracking (Optimal)

1. Use a queue for BFS traversal

2. Keep track of current level

3. For each level, collect all nodes

4. Reverse the order for odd levels

5. Add the level to result

Approach 2: Two Stacks

1. Use two stacks: one for current level, one for next level

2. Process current level stack

3. Push children to next level stack in reverse order

4. Swap stacks when current level is empty

Approach 3: BFS with Deque

1. Use a deque (double-ended queue)

2. Add nodes from front for even levels

3. Add nodes from back for odd levels

4. Process level by level

Dry Run

Let's trace through Example 1: root = [3,9,20,null,null,15,7]

BFS with Level Tracking:

• Initialize: queue = [3], level = 0, result = []
• Level 0: queue = [3]
• Process: current = 3, level = 0 (even)
• Add children: queue = [9, 20]
• Add to result: [[3]]
• Level 1: queue = [9, 20]
• Process: current = 9, level = 1 (odd)
• Process: current = 20, level = 1 (odd)
• Add children: queue = [15, 7]
• Reverse level: [20, 9]
• Add to result: [[3], [20, 9]]
• Level 2: queue = [15, 7]
• Process: current = 15, level = 2 (even)
• Process: current = 7, level = 2 (even)
• Add to result: [[3], [20, 9], [15, 7]]

Key Insights

1. Level Tracking: Use a counter or flag to track current level

2. Direction Alternation: Even levels (0, 2, 4...) go left to right, odd levels (1, 3, 5...) go right to left

3. BFS Structure: Process nodes level by level using a queue

4. Reversal Strategy: Collect all nodes at a level, then reverse if needed

Edge Cases

1. Empty Tree: Return empty array

2. Single Node: Return [[root.val]]

3. Linear Tree: Handle single path correctly

4. Complete Tree: Handle all levels properly

Solutions

Best Approach: BFS with Level Tracking

• Time Complexity: O(n) where n is the number of nodes
• Space Complexity: O(n) for the queue
• Key Idea: Use BFS with level-based reversal

Average Approach: Two Stacks

• Time Complexity: O(n)
• Space Complexity: O(n)
• Key Idea: Use two stacks to alternate direction

Worst Approach: BFS with Deque

• Time Complexity: O(n)
• Space Complexity: O(n)
• Key Idea: Use deque operations for direction control

More Microsoft coding questions