Zigzag Level Order Traversal in DSA Typescript - Time & Space Complexity

Time Complexity: Zigzag Level Order Traversal

O(n^2)

Understanding Time Complexity

We want to understand how the time needed to traverse a tree in zigzag order grows as the tree gets bigger.

Specifically, how does the number of nodes affect the steps taken?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

function zigzagLevelOrder(root: TreeNode | null): number[][] {
  if (!root) return [];
  const result: number[][] = [];
  const queue: TreeNode[] = [root];
  let leftToRight = true;

  while (queue.length) {
    const levelSize = queue.length;
    const levelNodes: number[] = [];
    for (let i = 0; i < levelSize; i++) {
      const node = queue.shift()!;
      if (leftToRight) levelNodes.push(node.val);
      else levelNodes.unshift(node.val);
      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }
    result.push(levelNodes);
    leftToRight = !leftToRight;
  }
  return result;
}
    

This code visits each node of a binary tree level by level, alternating the order of values collected per level.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The while loop runs once per tree level, and the inner for loop visits every node in that level.
• How many times: Every node in the tree is visited exactly once during the traversal.

How Execution Grows With Input

As the number of nodes (n) grows, the code visits each node once, but unshift operations on level arrays add extra cost up to quadratic per level.

Input Size (n)	Approx. Node Visits
10	About 10 visits and value insertions
100	About 100 visits and value insertions
1000	About 1000 visits and value insertions

Pattern observation: Node visits grow linearly with n, but total time can grow quadratically due to unshift costs.

Final Time Complexity

Time Complexity: O(n^2)

This means the time to complete the traversal can grow quadratically with the number of nodes in the worst case.

Common Mistake

[OK] Correct thinking: "Because we use unshift inside the loop, the time complexity becomes quadratic."

Why: For a level with k nodes, k sequential unshifts take O(1 + 2 + ... + k) = O(k^2) time. Worst case k=Θ(n), so O(n^2) overall.

Interview Connect

Understanding this traversal's time complexity helps you explain how tree traversals work efficiently, a common topic in interviews.

Self-Check

"What if we replaced the array unshift with a different data structure like a deque? How would that affect the time complexity?"