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

Time Complexity: Zigzag Level Order Traversal

O(n)

Understanding Time Complexity

We want to understand how the time needed grows when we do a zigzag level order traversal of a tree.

How does the number of steps change as the tree gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

function zigzagLevelOrder(root) {
  if (!root) return [];
  const result = [];
  const queue = [root];
  let leftToRight = true;

  while (queue.length) {
    const levelSize = queue.length;
    const levelNodes = [];

    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 level by level, switching direction each level to create a zigzag pattern.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

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

How Execution Grows With Input

As the number of nodes (n) grows, the code visits each node once, so the total steps grow roughly in direct proportion to n.

Input Size (n)	Approx. Operations
10	About 10 visits
100	About 100 visits
1000	About 1000 visits

Pattern observation: The number of operations grows linearly with the number of nodes.

Final Time Complexity

Time Complexity: O(n)

This means the time needed grows directly with the number of nodes in the tree.

Common Mistake

[X] Wrong: "Because we use unshift inside the loop, the time complexity becomes quadratic O(n²)."

[OK] Correct: Although unshift can be costly, it is done only for nodes at each level, and since each node is processed once, the total work remains proportional to n.

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 used for levelNodes with a deque to avoid unshift? How would the time complexity change?"