← Microsoft Interview Insights

Microsoft·Software Engineer·Technical Phone Screen·Intermediate

Intermediate
May 2026

Summary

Got a Microsoft coding round with a tree traversal problem. Nothing too wild but the alternating direction part tripped me up more than I expected.

Questions Asked (1)

Q1

Given the root of a binary tree, return the zigzag level order traversal of its node values, alternating left-to-right and right-to-left at each level.

Algorithms & Data Structures
Author's notes

BFS was the obvious starting point and I got there, but I fumbled the direction-switching logic for longer than I'd like to admit.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Use BFS with a queue to process nodes level by level, tracking the current level number. For each level, collect node values in a list, and if the level is odd (0-indexed), reverse the list before adding to the result. This ensures alternating left-to-right and right-to-left order.

Pro tip: Mention that you can avoid reversing the list by using a deque and appending to the front for right-to-left levels, which is more efficient. Also, clarify that the root level is considered left-to-right.

1. Clarify the problem

Confirm that the traversal starts with left-to-right at the root level, and that zigzag alternates each subsequent level. Ask about edge cases like empty tree.

2. Choose BFS with a queue

Explain that level-order traversal naturally uses a queue. Initialize a queue with the root and a level counter starting at 0.

3. Process each level

While the queue is not empty, determine the number of nodes at the current level. Dequeue that many nodes, collect their values, and enqueue their children.

4. Handle zigzag order

If the current level is odd, reverse the collected values (or use a deque to insert at front) before adding to the result. Increment the level counter.

5. Return the result

After processing all levels, return the list of lists containing the zigzag level order traversal.

Key Points to Mention

  • BFS with a queue is ideal for level-order traversal.
  • Use a level counter to determine direction (even: left-to-right, odd: right-to-left).
  • Time complexity is O(N) where N is number of nodes, as each node is visited once.
  • Space complexity is O(W) where W is the maximum width of the tree, due to queue size.
  • Edge cases: empty tree returns empty list; single node returns [[root.val]].
  • Alternative: use deque and appendleft for odd levels to avoid reversing.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.