Skip to main content
Talentd

Zigzag Level Sum of Binary Tree - Solution & Explanation

MediumPremiumFree on FleetCode10 min read
Practice this problem

Problem Statement

You are given the root of a binary tree.

Traverse the tree level by level using a zigzag pattern:

  • At odd-numbered levels (1-indexed), traverse nodes from left to right.
  • At even-numbered levels, traverse nodes from right to left.

While traversing a level in the specified direction, process nodes in order and stop immediately before the first node that violates the condition:

  • At odd levels: the node does not have a left child.
  • At even levels: the node does not have a right child.

Only the nodes processed before this stopping condition contribute to the level sum.

Return an integer array ans where ans[i] is the sum of the node values that are processed at level i + 1.

 

Example 1:

Input: root = [5,2,8,1,null,9,6]

Output: [5,8,0]

Explanation:

ā€‹ā€‹ā€‹ā€‹ā€‹ā€‹ā€‹

  • At level 1, nodes are processed left to right. Node 5 is included, thus ans[0] = 5.
  • At level 2, nodes are processed right to left. Node 8 is included, but node 2 lacks a right child, so processing stops, thus ans[1] = 8.
  • At level 3, nodes are processed left to right. The first node 1 lacks a left child, so no nodes are included, and ans[2] = 0.
  • Thus, ans = [5, 8, 0].

Example 2:

Input: root = [1,2,3,4,5,null,7]

Output: [1,5,0]

Explanation:

  • At level 1, nodes are processed left to right. Node 1 is included, thus ans[0] = 1.
  • At level 2, nodes are processed right to left. Nodes 3 and 2 are included since both have right children, thus ans[1] = 3 + 2 = 5.
  • At level 3, nodes are processed left to right. The first node 4 lacks a left child, so no nodes are included, and ans[2] = 0.
  • Thus, ans = [1, 5, 0].

 

Constraints:

  • The number of nodes in the tree is in the range [1, 105].
  • -105 <= Node.val <= 105

Approach Overview

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.

Solution

We use a queue q to perform a level-order traversal, and define a boolean variable left to indicate the traversal direction of the current level. For each level, we first add the nodes of the next level to the queue nq, and then compute the sum of the node values of the current level, denoted by s, according to the value of left, and append s to the answer array. Finally, we update the value of left and assign nq to q to continue traversing the next level.

The time complexity is O(n), and the space complexity is O(n). Here, n is the number of nodes in the binary tree.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor ā†’

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Height-Based Level ScanO(n^2)O(h)Conceptual understanding of tree levels; acceptable for small trees
BFS Level Order with QueueO(n)O(w)Best general solution; processes nodes exactly once
DFS with Level TrackingO(n)O(h)Useful when recursion is preferred or when already using DFS patterns

Frequently Asked Questions

Is Zigzag Level Sum of Binary Tree easy or hard?
This problem is typically classified as medium difficulty. It requires understanding binary tree traversal, especially BFS level order traversal, and managing level boundaries while maintaining a zigzag traversal pattern.
Zigzag Level Sum of Binary Tree Python/Java solution
Most Python and Java implementations use a queue for BFS. Initialize a queue with the root node, iterate level by level, compute the sum for each level, and toggle a direction flag after each iteration. This produces an O(n) time solution with straightforward code in both languages.
How to solve Zigzag Level Sum of Binary Tree in O(n)?
Perform a BFS traversal using a queue. For each level, determine the number of nodes currently in the queue, process exactly that many nodes, and accumulate their values into a level sum. Push children into the queue for the next level and toggle a direction flag to maintain zigzag order. Since each node is visited once, the algorithm runs in O(n).
What is the best approach for Zigzag Level Sum of Binary Tree?
Breadth-first search (BFS) level order traversal with a queue is the most practical approach. Process the tree one level at a time, sum node values in that level, and alternate traversal direction logically to match the zigzag pattern. This approach visits each node exactly once and runs in O(n) time with O(w) space where w is the maximum width of the tree.
Is Zigzag Level Sum of Binary Tree asked at Google/Amazon/Meta?
Binary tree level-order and zigzag traversal variants frequently appear in interviews at companies like Amazon, Google, and Meta. Problems combining BFS traversal with level-based aggregation (such as sums or averages) are common follow-ups to standard zigzag level order traversal questions.
What data structure is used in Zigzag Level Sum of Binary Tree?
A queue is the primary data structure used for level order traversal in BFS. Some implementations also use a deque or stack to control traversal direction for zigzag patterns. For DFS solutions, recursion with an array or list indexed by depth is typically used.
What is the time complexity of Zigzag Level Sum of Binary Tree?
The optimal solution runs in O(n) time because every node in the binary tree is processed exactly once during traversal. Space complexity is O(w) for BFS where w is the maximum width of the tree, or O(h) for DFS where h is the tree height.

Ready to solve this problem?

Practice Zigzag Level Sum of Binary Tree with our built-in code editor and test cases.

Practice on FleetCode