What is the brute force approach and complexity for Binary Tree Zigzag Level Order Traversal?

Run the normal level order, then std::reverse every odd-numbered row with time complexity O(N) and space complexity O(N).

What is the optimal approach and complexity for Binary Tree Zigzag Level Order Traversal?

Level order as usual; on right-to-left rows write each value at size − 1 − i with optimal time complexity O(N) and space complexity O(N).

How do you identify the pattern for Binary Tree Zigzag Level Order Traversal?

Look for key signals in the prompt: "zigzag" indicates The same rows as LC 102, but the direction flips from row to row.; "left to right, then right to left" indicates Two write orders for the same pop order. The queue stays the same.; "level by level" indicates Still a BFS question: rounds of `size` nodes..

Binary Tree Zigzag Level Order Traversal

Medium·LeetCode #103 Pro OnlyMedium

LeetCode

Problem Statement

You are given the root of a binary tree. Return the node values one row at a time, from the top down, like a normal level order traversal. But the direction alternates from row to row:

Row 0 (the root) goes left to right.
Row 1 goes right to left.
Row 2 goes left to right again, and so on.

Each row becomes one inner list in the answer. An empty tree gives an empty answer.

Input

The root of a binary tree. It can be empty (null).

In the examples, a tree is written in level order: the root first, then each row left to right. A null marks a missing child.

Output

A list of rows, where each row is read in the zigzag direction for its level.

Example 1

Input: root = [3, 9, 20, null, null, 15, 7]

Output: [[3], [20, 9], [15, 7]]

Row 0 is 3. Row 1 is 9 and 20, read right to left as 20, 9. Row 2 is 15 and 7, read left to right.

Example 2

Input: root = [1]

Output: [[1]]

A single node is one row.

Example 3

Input: root = []

Output: []

No nodes, so no rows.

Constraints

• The number of nodes in the tree is in the range [0, 2000].
• −100 ≤ Node.val ≤ 100

Pattern Recognition Clues

Recognising these key signals in the problem description immediately identifies the pattern:

“zigzag”

→ The same rows as LC 102, but the direction flips from row to row.

“left to right, then right to left”

→ Two write orders for the same pop order. The queue stays the same.

“level by level”

→ Still a BFS question: rounds of `size` nodes.

Approach Complexity Ladder

Brute Force — plain level order, then reverse the odd rowsO(N)O(N)

Run the normal level order, then std::reverse every odd-numbered row

Optimal — BFS, write each value into its slotO(N)O(N)

Level order as usual; on right-to-left rows write each value at size − 1 − i

Brute Force Intuition

Run the LC 102 level order traversal to get every row left to right. Then call reverse on each odd-numbered row (rows 1, 3, 5, …). Each row is reversed once, so the zigzag comes out right.

Recognition rule for this sub-pattern:

Pop exactly `size` nodes per round; that round is one level.

Remember this · Tree BFS

Trigger

Level order, per-level max/average, right side view, minimum depth, nodes at distance k.

Think

Does the question care about depth / rows rather than paths?

Key question

How many nodes are in the current level (queue size at the start of the level)?

Brute2Best Pro Content

Unlock Complete Visual Walkthrough & Optimal C++

The interactive animated dry-run player, optimized C++ implementation, state invariant derivations, and edge-case breakdown for this question are part of Brute2Best Pro. The anchor question of every sub-pattern is completely free.

All 440 visual dry runs & algorithms

Interactive step-by-step playback with pointer & array state transitions

52 comprehensive LLD chapters

Interactive UML diagrams, real-world stories (Food Delivery, Trading, RPG), and practice solutions

40 C++ basics labs & hardware memory models

Vtables, byte layouts, assembly insights, and multi-threading race conditions

Production-ready C++23 source code

Modern idioms, clean contracts, time/space complexity derivations, and interview takeaways

Create Free Account Log in

First anchor question per pattern, Part 1 LLD & Module 1 C++ basics are 100% Free forever.

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like Tree BFS translate into production architectures and low-level memory mechanics.

LLD Architecture