Problem 103

Abstract / Summary

Return node values level by level in a zigzag pattern alternating direction each level.

Note

The full problem description, including helpful examples, can be found on LeetCode.

Python 0103.py

class Solution:
    def zigzagLevelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        # similiar to problem 102
        levels = defaultdict(list)

        def deeper(node, depth):
            if node:
                levels[depth].append(node.val)
                deeper(node.left,  depth+1)
                deeper(node.right, depth+1)

        deeper(root, 0)

        for l in levels.keys():
            if l % 2 == 1:
                levels[l] = reversed(levels[l])

        return [ levels[l] for l in sorted(levels.keys()) ]
18 lines | 564 bytes | submitted August 31, 2023 | GitHub   7% comment ratio | tab size 4 | low complexity

Difficulty

This problem is ranked as
easy medium hard

and has an acceptance rate of about 64% (2+ million submissions).

Typical patterns to solve this problem:
  • Binary Tree
  • Breadth First Search
  • Tree
I solved 663 easy, 1250 medium and 309 hard problems

AI Disclaimer

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.
LeetCode profile | GitHub repo

Code Walkthrough

Overview

The provided implementation defines a Solution class with a method zigzagLevelOrder that returns the values of a binary tree in a zig-zag (alternating left-to-right and right-to-left) level order traversal. The algorithm first collects node values per depth using a depth-first recursion, then reverses the order of values on every odd-indexed level, and finally assembles the result in increasing depth order.

Key Steps

The method begins by creating a dictionary that maps each depth to a list of node values encountered at that depth.

levels = defaultdict(list)

A nested helper function deeper performs a pre-order depth-first walk. For each non-null node it records the node’s value in the list associated with the current depth, then recurses on the left child followed by the right child, incrementing the depth counter.

def deeper(node, depth):
    if node:
        levels[depth].append(node.val)
        deeper(node.left,  depth+1)
        deeper(node.right, depth+1)

The recursion is initiated with the root node at depth zero.

deeper(root, 0)

After the traversal, the code iterates over the collected depth keys. For each odd depth it replaces the list with a reversed iterator, thereby achieving the required right-to-left ordering for those levels.

for l in levels.keys():
    if l % 2 == 1:
        levels[l] = reversed(levels[l])

Finally, the method builds the output list by extracting the values for each depth in sorted order, preserving the original or reversed ordering as appropriate.

return [ levels[l] for l in sorted(levels.keys()) ]

Edge Cases Handled

When the input root is None, the recursive helper receives a null node immediately, performs no append operation, and the levels dictionary remains empty. The subsequent loop over levels.keys() does nothing, and the final list comprehension yields an empty list, correctly representing an empty tree.

If the tree consists of a single node, the recursion records the node’s value at depth zero. Since depth zero is even, no reversal occurs, and the result is a list containing a single inner list with that value.

The use of defaultdict(list) ensures that any depth encountered for the first time is automatically associated with an empty list, eliminating the need for explicit existence checks before appending.

Reversal is applied only to odd depths, so levels that naturally appear left-to-right (even depths) retain their original order without additional processing.

Performance Optimizations

The algorithm leverages a single depth-first traversal to populate all levels, avoiding the need for multiple passes or auxiliary queues typically used in breadth-first approaches. By storing values directly into a dictionary keyed by depth, the method eliminates repeated list concatenations.

The reversal step uses Python’s built-in reversed iterator, which provides a lazy view of the list in reverse order without creating a new list copy. This reduces memory overhead for large levels where a full copy would be unnecessary.

Sorting the depth keys before constructing the final result incurs a cost proportional to the number of distinct depths, which is bounded by the height of the tree. Since the number of depths is usually far smaller than the total node count, this sorting step has minimal impact on overall performance.

Collecting all node values during the recursive walk ensures that each node is visited exactly once, leading to a linear traversal cost relative to the number of nodes. The combination of a single pass, lazy reversal, and efficient dictionary access results in a solution that scales well for deep or wide binary trees.

written by openai gpt

ELI5 - Simplified Explanation

Imagine a giant tree made of numbers. To read them, you start at the very top and look at each row one by one. The code starts at the top and visits every single number in the tree, grouping them together based on how far down they are. Every row gets its own special basket.

Once every number is tucked into its correct row basket, the code looks at them again. It decides to leave the first row exactly as it is. For the next row down, it turns the numbers around so they are in backwards order. It keeps switching back and forth like this, leaving one row normal and flipping the next one, all the way down the tree. It looks just like a zigzagging path through the branches. The final result is a list of these baskets, arranged perfectly from top to bottom with some rows walking in reverse.

written by google gemini

Code Quality

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):
n = 27 | median = 7 | μ = 6.30 | σ = 1.44

Complexity Analysis

not analyzed yet

Other Solutions

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)
author
author solutions
www AlgoMonster C++ Python Java TS
WalkCCC C++ Python Java
leetcode.ca C++ Python Java Rust JS Go TS
LeetcodeHelp C++ Python Java
MemoryLimitExceeded C++ Python
Progiez C++ Python Java
github AdelDaniel Dart
aylei Rust
begeekmyfriend C
BigEggStudy C#
black-shadows Python
charles-wangkai Java
chenyanzhe C++
everthis JS
fartem Ruby
FelixFan1122 C#
fengvyi C++
gaosq0604 Python
Garvit244 Python
halfrost Go
haoel C++
JoshCrozier JS
keineahnung2345 C++
Krazune C++
lennylxx C++
linouk23 C++
lkwq007 Python
luangong C++
MacJim C++
qiyuangong Python
ruoru Rust
shreymehul C#
sonugiri1043 C++
suxrobGM C#
varunu28 Java
vli02 C
vthwang Java
XiaotaoGuo C++
yuanliu666 Kotlin
YuriSpiridonov Python
zfang399 C++
AlgoMonster C++, Python, Java, TypeScript
WalkCCC C++, Python, Java
leetcode.ca C++, Go, Java, JavaScript, Python, Rust, TypeScript
LeetcodeHelp C++, Java, Python
MemoryLimitExceeded Python, C++
Progiez C++, Java, Python
AdelDaniel Dart
aylei Rust
begeekmyfriend C
BigEggStudy C#
black-shadows Python, Python
charles-wangkai Java
chenyanzhe C++
everthis JavaScript
fartem Ruby
FelixFan1122 C#
fengvyi C++
gaosq0604 Python
Garvit244 Python
halfrost Go
haoel C++
JoshCrozier JavaScript
keineahnung2345 C++
Krazune C++
lennylxx C++
linouk23 C++
lkwq007 Python
luangong C++
MacJim C++
qiyuangong Python
ruoru Rust
shreymehul C#
sonugiri1043 C++
suxrobGM C#
varunu28 Java
vli02 C
vthwang Java
XiaotaoGuo C++
yuanliu666 Kotlin
YuriSpiridonov Python
zfang399 C++
57 links | 41 authors | 12 languages

Videos

These are a few popular YouTube videos for this problem:
YouTube video 'Coding Interview Tutorial 16: Binary Tree Zigzag Level Order Traversal [LeetCode]'
Amell Peralta 10 mins
Coding Interview Tutorial 16: Binary Tree Zigzag Level Order Traversal [LeetCode]
YouTube video 'binary tree zigzag level order traversal leetcode 103'
Naresh Gupta 11 mins
binary tree zigzag level order traversal leetcode 103
YouTube video 'Binary Tree Zigzag Level Order Traversal | Leet code 103 | Theory explained + Python code'
Sai Anish Malla 6 mins
Binary Tree Zigzag Level Order Traversal | Leet code 103 | Theory explained + Python code
YouTube video 'Binary Tree Zigzag Level Order Traversal | Day 22 | [ July LeetCoding Challenge ] [ Leetcode #103 ]'
Algorithms Made Easy 5 mins
Binary Tree Zigzag Level Order Traversal | Day 22 | [ July LeetCoding Challenge ] [ Leetcode #103 ]
YouTube video 'Binary Tree Zigzag Level Order Traversal | LeetCode 103'
Michael Vandi 11 mins
Binary Tree Zigzag Level Order Traversal | LeetCode 103
YouTube video 'Binary Tree Zigzag Level Order Traversal - LeetCode 103 - JavaScript'
AlgoJS 7 mins
Binary Tree Zigzag Level Order Traversal - LeetCode 103 - JavaScript
YouTube video 'Leetcode 103 Binary Tree Zigzag Level Order Traversal (Java) - Beats 100%'
TheAnalyticGuy 9 mins
Leetcode 103 Binary Tree Zigzag Level Order Traversal (Java) - Beats 100%
YouTube video '103 ||  Binary Tree Zigzag Level Order Traversal II || C++ || Leetcode Daily Challenge'
CodeFreaks 14 mins
103 || Binary Tree Zigzag Level Order Traversal II || C++ || Leetcode Daily Challenge
YouTube video '103. Binary Tree Zigzag Level Order Traversal | JavaScript | LeetCode Daily Challenge'
LeetCodeWithMonu 13 mins
103. Binary Tree Zigzag Level Order Traversal | JavaScript | LeetCode Daily Challenge
YouTube video 'MICROSOFT Coding Interview Question - Binary Tree Zigzag Level Order Traversal | LeetCode'
JeanTheCoder 12 mins
MICROSOFT Coding Interview Question - Binary Tree Zigzag Level Order Traversal | LeetCode
YouTube video 'Leetcode 103: Binary Tree Zigzag Level Order Traversal'
Algorithms Casts 29 mins
Leetcode 103: Binary Tree Zigzag Level Order Traversal
YouTube video '103. Binary Tree Zigzag Level Order Traversal | Leetcode | Binary Tree | DSA'
Coding with Tamilarasan 19 mins
103. Binary Tree Zigzag Level Order Traversal | Leetcode | Binary Tree | DSA
YouTube video 'Daily Leetcode #1055: Feb 19, 2023 - 103. Binary Tree Zigzag Level Order Traversal'
Programming Live with Larry 5 mins
Daily Leetcode #1055: Feb 19, 2023 - 103. Binary Tree Zigzag Level Order Traversal
YouTube video 'Daily Leetcode #113: Jul 22, 2020 - 103. Binary Tree Zigzag Level Order Traversal'
Programming Live with Larry 10 mins
Daily Leetcode #113: Jul 22, 2020 - 103. Binary Tree Zigzag Level Order Traversal
YouTube video 'Day 241: LeetCode Problem 103. Binary Tree Zigzag Level Order Traversal - Swift'
iOSxBank 13 mins
Day 241: LeetCode Problem 103. Binary Tree Zigzag Level Order Traversal - Swift
YouTube video 'Apple Coding Interview Question | Leetcode 103 | Binary Tree Zigzag Level Order Traversal'
WorkWithGoogler 10 mins
Apple Coding Interview Question | Leetcode 103 | Binary Tree Zigzag Level Order Traversal
YouTube video 'LeetCode 103 Binary Tree Zigzag Level Order Traversal'
Jeevan Kumar - Cracckify 10 mins
LeetCode 103 Binary Tree Zigzag Level Order Traversal
YouTube video 'LeetCode 103: Binary Tree Zigzag Level Order Traversal | C# Solution | BFS |'
Code Scribbler 6 mins
LeetCode 103: Binary Tree Zigzag Level Order Traversal | C# Solution | BFS |
YouTube video 'LeetCode 103. [Medium] Binary Tree Zigzag Level Order Traversal'
Francesco Manicardi 3 mins
LeetCode 103. [Medium] Binary Tree Zigzag Level Order Traversal
YouTube video 'Binary Tree Zigzag Level Order Traversal | Leetcode 103 | Approach + Code with explanation.'
Pirai's Academy 13 mins
Binary Tree Zigzag Level Order Traversal | Leetcode 103 | Approach + Code with explanation.
20 videos   did my crawler come up with invalid videos ? drop me a line.

Similar Problems

2 similar problems

Solved On The Same Day

27 solutions   August 31, 2023

Extra

There are a few extra pages giving you some insights into my setup:
  • Tech Stack - my development environment and tools
  • AI - how AI helped me create this website (NOT solving the problems)
  • Progress - progression over time
  • Quality - code quality