Zigzag Level Sum of Binary Tree - Solution & Explanation

Problem Overview: Given a binary tree, compute the sum of node values at each level while traversing the tree in zigzag order (left-to-right, then right-to-left for the next level). The result is an array where each element represents the sum of values at that level.

Approach 1: Level-by-Level Traversal (Brute Force Height Scan) (Time: O(n^2), Space: O(h))

First compute the height of the tree, then traverse the tree repeatedly for each level using a helper that collects values only from the current depth. Alternate traversal direction (left-first or right-first) depending on the level index to simulate zigzag order. While collecting nodes, accumulate their values into a level sum. Because the tree may be scanned again for every level, the worst-case time complexity becomes O(n^2) for skewed trees, with recursion stack space O(h).

Approach 2: BFS Level Order with Direction Flag (Optimal) (Time: O(n), Space: O(w))

Use a queue to perform breadth-first search. Process nodes level by level: pop k nodes from the queue (the current level size), sum their values, and push their children. Maintain a boolean flag to represent zigzag direction. The direction determines whether children are pushed normally or handled using a temporary structure such as a deque, though the level sum itself remains a simple accumulation. Each node is visited exactly once, giving O(n) time and O(w) auxiliary space where w is the maximum width of the tree.

Approach 3: DFS with Level Tracking (Time: O(n), Space: O(h))

Depth-first traversal also works if you track the current depth. Use recursion and maintain a dynamic array where index i stores the running sum for level i. When visiting a node, ensure the array has space for that level and add the node's value. Alternate traversal order (left/right or right/left) based on depth parity to mimic zigzag behavior. This approach visits every node once, producing O(n) time complexity with recursion stack space O(h). It relies on standard depth-first search patterns used in many binary tree problems.

Recommended for interviews: The BFS level-order traversal with a queue is the expected solution. It models the problem directly: process one level at a time and compute the sum during traversal. Mentioning the height-based brute force shows understanding of tree levels, but the BFS approach demonstrates practical knowledge of queue-based tree traversal and achieves optimal O(n) time.