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

Time Complexity: Zigzag Level Order Traversal

O(n)

Understanding Time Complexity

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

How does the number of steps grow when the tree has more nodes?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

func zigzagLevelOrder(root *TreeNode) [][]int {
    if root == nil {
        return [][]int{}
    }
    var result [][]int
    queue := []*TreeNode{root}
    leftToRight := true

    for len(queue) > 0 {
        levelSize := len(queue)
        level := make([]int, levelSize)
        for i := 0; i < levelSize; i++ {
            node := queue[0]
            queue = queue[1:]
            index := i
            if !leftToRight {
                index = levelSize - 1 - i
            }
            level[index] = node.Val
            if node.Left != nil {
                queue = append(queue, node.Left)
            }
            if node.Right != nil {
                queue = append(queue, node.Right)
            }
        }
        result = append(result, level)
        leftToRight = !leftToRight
    }
    return result
}
    

This code visits each node of a binary tree level by level, alternating the order of values between left-to-right and right-to-left.

Identify Repeating Operations

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

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 work grows linearly as the tree size increases.

Final Time Complexity

Time Complexity: O(n)

This means the time to complete the traversal grows directly with the number of nodes in the tree.

Common Mistake

[X] Wrong: "Because we have nested loops, the time complexity must be O(n²)."

[OK] Correct: The inner loop runs only for nodes at each level, and all nodes together are visited once total, so the total work is still proportional to n, not n squared.

Interview Connect

Understanding this traversal's time complexity helps you explain how tree traversals scale, a common topic in interviews. It shows you can analyze loops carefully, not just count nesting.

Self-Check

"What if we used a recursive approach instead of a queue? How would the time complexity change?"