Skip to main content

65. Binary Tree Zigzag Level Order Traversal

mediumAsked at Salesforce

Return the zigzag (alternating left-to-right, right-to-left) level-order traversal of a binary tree. Salesforce uses this as a BFS variant.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Source citations

Public interview reports confirming this problem appears in Salesforce loops.

  • Glassdoor (2026-Q1)— Salesforce uses this to test BFS-with-toggle.
  • LeetCode Discuss (2025)— Common pairing with LC 102.

Problem

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).

Constraints

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

Examples

Example 1

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

Example 2

Input
root = [1]
Output
[[1]]

Approaches

1. BFS then reverse alternating levels

Do standard BFS; reverse every other result row.

Time
O(n)
Space
O(w)
function zigzagLevelOrder(root) {
  if (!root) return [];
  const result = [], queue = [root];
  let leftToRight = true;
  while (queue.length) {
    const level = [], n = queue.length;
    for (let i = 0; i < n; i++) {
      const node = queue.shift();
      level.push(node.val);
      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }
    if (!leftToRight) level.reverse();
    result.push(level);
    leftToRight = !leftToRight;
  }
  return result;
}

Tradeoff: Simple and correct.

2. BFS with directional insertion

Insert at end (push) for left-to-right, at front (unshift) for right-to-left. No reverse needed.

Time
O(n)
Space
O(w)
function zigzagLevelOrder(root) {
  if (!root) return [];
  const result = [], queue = [root];
  let leftToRight = true;
  while (queue.length) {
    const level = [], n = queue.length;
    for (let i = 0; i < n; i++) {
      const node = queue.shift();
      if (leftToRight) level.push(node.val);
      else level.unshift(node.val);
      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }
    result.push(level);
    leftToRight = !leftToRight;
  }
  return result;
}

Tradeoff: Avoids the explicit reverse but unshift is O(n) per call. Theoretically the same asymptotic complexity due to the level-size cap.

Salesforce-specific tips

Salesforce treats this as a simple BFS variant — they grade primarily on whether you reach for the BFS pattern and toggle correctly. Bonus signal: discuss which insertion strategy is faster in practice (the explicit reverse approach is usually faster due to JS engine optimizations).

Common mistakes

  • Reversing the queue itself — corrupts the BFS order for children.
  • Forgetting to toggle leftToRight at end of loop.
  • Using unshift in a tight loop without realizing it's O(n).

Follow-up questions

An interviewer at Salesforce may pivot to one of these next:

  • Binary Tree Level Order Traversal (LC 102).
  • Binary Tree Right Side View (LC 199).
  • N-ary Tree Level Order Traversal.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

Should I reverse the queue or the result row?

Reverse the result row only. Reversing the queue would mess up the children's order for subsequent levels.

Why is unshift O(n)?

Inserting at the front of an array reindexes all subsequent elements. The total work is still O(n) per level due to the cap, but with worse constants than push.

Practice these live with InterviewChamp.AI

Drill Binary Tree Zigzag Level Order Traversal and other Salesforce interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →