What is the pricing and subscription model for Hi👋SpeedAlgo?

The entire core curriculum of 13 patterns and 225 practice problems is 100% free to access with no credit card required. New accounts get 40 free coins once, the daily claim adds +20 coins once a day, and inviting a friend earns you +25 coins when they complete their first practice step. These are the only ways to earn coins. Each AI coach question costs 1-5 coins, priced by the server according to its size. AI coaching is free with your own Google Gemini, OpenAI or OpenRouter API key (BYOK). Coins also unlock extras for 24 hours: a Recall hint level (1 coin), a Solve solution reveal (2), a LeetCode problem card's solutions (1) and a pattern's extra canonical problems (1). Nothing on the site is sold for money: coins can only be earned, never bought.

What is the refund and cancellation policy?

Hi👋SpeedAlgo sells nothing for money: there are no subscriptions, renewals or charges, so there is nothing to cancel or refund. Nothing on the site is sold for money: coins can only be earned, never bought.

Who creates and maintains the curriculum?

Hi👋SpeedAlgo is developed and maintained by Hi👋WebEnterprise (https://hiwebenterprise.com), an engineering organization focused on developer education, deliberate practice methodologies, and cognitive ergonomics for technical interviews.

How does Hi👋SpeedAlgo prepare candidates for senior and staff SWE interviews?

Rather than rote LeetCode grinding, Hi👋SpeedAlgo uses deliberate practice for each pattern: learn the loop invariant, Big-O proof and edge cases from a side-by-side template and a step-by-step debugger, rebuild the template from memory, then solve a new problem on your own against a graded test suite.

Theory Context•Breadth-First Search (BFS)

P0EasyMental model~6 min speedrun

Level Order Traversal (BFS by Level)

Grows into

Topological Sort Multi-Source BFS Graph BFS

Unlocks

Shortest-Path BFS

The problem

Binary Tree Level Order Traversal (LC 102)(opens leetcode.com)

You have the root of a binary tree. Walk it breadth-first, visiting each depth in left-to-right order, and produce one list of values per depth — so the result is a list of lists, ordered from the root's level down to the leaves' level.

Example 1

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

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

Depth 0 holds 3, depth 1 holds 9 and 20, depth 2 holds 15 and 7.

Level-Order BFS

root ➔ freeze level_size = len(queue) ➔ batch process ring

Spot it when: The output is grouped by depth: one list per level, zigzag order, the rightmost node or the sum of each level.

Level-Order BFS

Python

1	from collections import deque
2	from typing import Callable, Iterable, List, Optional, TypeVar
3
4	Item = TypeVar("Item")
5
6	class TreeNode:
7	def __init__(self, val: int = 0, left: Optional["TreeNode"] = None, right: Optional["TreeNode"] = None):
8	self.val = val
9	self.left = left
10	self.right = right
11
12
13	def level_by_level(start: Iterable[Item], children: Callable[[Item], Iterable[Item]], record: Callable[[List[Item]], None]) -> None:
14	"""Level-Order BFS: hand the nodes of each level, left to right, to record(level), level after level.
15	start is the first level. children(node) lists the nodes of the next level below node.
16	Precondition: every node is reached once, as in a tree, or children skips the nodes already seen.
17	V = the nodes. W = the largest level. T = the cost of one children call, or of record for one node.
18	Time: O(V * T) \| Space: O(W) queue and current level
19	"""
20	queue = deque(start) # holds nodes queued for this or a later level, in enqueue order
21
22	while queue:
23	# 1. Snapshot the Level Boundary:
24	# len(queue) right now counts only nodes queued from the previous level, so
25	# freezing it before the inner loop keeps this level's own children out of
26	# the current sweep.
27	level_size = len(queue)
28	current_level = []
29
30	for _ in range(level_size):
31	# 2. Pop and Record This Level's Node:
32	# popleft() returns nodes in the order they were queued, so the
33	# earliest-queued node is always processed first.
34	node = queue.popleft()
35	current_level.append(node)
36	queue.extend(children(node))
37
38	# 3. Record the Completed Level:
39	record(current_level)

Invariant: At the start of each round, queue holds exactly the nodes of one level, left to right, and level_size is their count.

Read len(queue) into level_size at the start of each round: exactly that many nodes belong to the current level. Process only those, adding their children, and the queue then holds just the next level. That gives level boundaries without storing a depth per node. The trap is re-reading the size while children arrive: the queue grows during the round, so a bound that checks len(queue) again (a while loop, or a loop in another language) runs on into the next level; freeze it in level_size first.

See it run

Level-Order BFS on root = [3, 9, 20, null, null, 15, 7], step by step

level_size 0len(queue) 1current_level []levels []

Each column is one node, in the order it is added to queue. The top row is queue. The bottom row shows a node's value once it is popped.

node the node popped now
in level a node of this level that is waiting
queued a node just added to the queue
level a node of the level that was just recorded

queue = deque([root]) holds the root 3. It is level 0.

queue

3queued

popped

1 / 16

Gotchas1 of 4

The trap
Gotcha 1: Looping while queue inside the round
Mistake
```
while queue:
```
Fix
```
for _ in range(level_size):
```
What happens: Children are added to the back of queue during the round. while queue keeps popping them in the same round. So the loop runs on into the next level, and every node ends up in one list. level_size = len(queue) is read once, before any child is added. The inner loop runs exactly that many times.
Example: Binary Tree Level Order Traversal (LC 102): root = [3,9,20,null,null,15,7]
Mistake: returns [[3, 9, 20, 15, 7]]Fix: returns [[3], [9, 20], [15, 7]]
Gotcha 2: Reading queue[-1] after the round instead of before it
Mistake
```
for _ in range(level_size):
    ...
view.append(queue[-1].val)
```
Fix
```
view.append(queue[-1].val)
for _ in range(level_size):
    ...
```
What happens: Binary Tree Right Side View (LC 199) keeps the last node of each level. Before the round, queue[-1] is that node. After the round, the queue holds the next level, so queue[-1] is the next level's last node. After the last level the queue is empty, and queue[-1] raises an IndexError.
Example: root = [1,2,3,null,5,null,4]
Mistake: raises IndexErrorFix: returns [1, 3, 4]
Gotcha 3: Running it on a graph without a seen set
Mistake
```
queue.append(nxt)
```
Fix
```
if nxt not in seen:
    seen.add(nxt)
    queue.append(nxt)
```
What happens: In a tree, each node has one parent, so it is added once. In a graph, two nodes can both point to the same node. Without seen, that node is added once per edge into it. In the example, node 3 appears twice in its level. Mark each node when you add it, as in Shortest-Path BFS.
Example: adj = {0: [1, 2], 1: [3], 2: [3], 3: []}, start = 0
Mistake: returns [[0], [1, 2], [3, 3]]Fix: returns [[0], [1, 2], [3]]
Gotcha 4: Using list.pop(0) instead of deque.popleft()
Mistake
```
node = queue.pop(0)
```
Fix
```
node = queue.popleft()
```
What happens: list.pop(0) moves every other item one place to the left, so it costs O(n) time. BFS pops every node once, so the whole walk costs O(n^2) time. collections.deque removes from the front in O(1) time. The answer is the same, only slower.

Not this one if…

You need the length of the shortest route to one target cell, as in Shortest Path in Binary Matrix (LC 1091), not the nodes grouped by level. See Shortest-Path BFS

Deep Dive

Why `level_size` marks the level boundary

A queue gives first in, first out order. In a tree, every node of depth d is added to queue before any node of depth d + 1, because depth d + 1 nodes are added only while depth d nodes are being popped. So the queue always holds the nodes of one depth, then the nodes of the next depth, with no mixing.

At the start of a round, queue holds exactly one level. level_size = len(queue) is the number of nodes in that level. The inner loop pops exactly level_size nodes. The children they add go behind them, so they cannot be reached in this round.

In Binary Tree Level Order Traversal (LC 102) with root = [3, 9, 20, null, null, 15, 7], the rounds read level_size = 1, 2 and 2. They produce [[3], [9, 20], [15, 7]]. No depth is stored per node. The size of the queue at the start of the round is enough.

The trap: the queue grows during the round

queue.extend and queue.append run inside the round, so len(queue) changes while the loop runs. After 3 is popped and its children are added, len(queue) is 2, but level_size is still 1. The round must stop here.

If the loop is while queue: instead of for _ in range(level_size):, the round does not stop. It pops 9 and 20 in the same round, then 15 and 7. For root = [3, 9, 20, null, null, 15, 7], the result is [[3, 9, 20, 15, 7]] instead of [[3], [9, 20], [15, 7]].

In Python, range(level_size) is built once, so it cannot change. In a language where the loop condition is checked again each time, writing i < queue.size() has the same fault as while queue. Always copy the size into level_size first.

Where to read the level: before, during or after the round

Each problem on the card asks for one value per level. Where you read it decides the answer.

Binary Tree Right Side View (LC 199) needs the last node of each level. Read queue[-1] before the round, when queue still holds only this level. After the round, queue holds the next level, and after the last level it is empty, so queue[-1] raises IndexError. For root = [1, 2, 3, null, 5, null, 4], reading before gives [1, 3, 4].

Average of Levels in Binary Tree (LC 637), Find Largest Value in Each Tree Row (LC 515) and Maximum Level Sum of a Binary Tree (LC 1161) read each popped node.val inside the round and combine the values after it. Binary Tree Zigzag Level Order Traversal (LC 103) reverses current_level on every second level, either with a flag or with level_index % 2.

Deepest Leaves Sum (LC 1302) keeps only the last current_level, because the last level that is recorded is the deepest one.

The cost, and what changes on a graph

Every node is added once and popped once. Each pop does constant work in levelOrder, so the time is O(V * T), which is O(N) for a tree with N nodes. The space is O(W). W is the largest number of nodes in one level, because queue and current_level hold at most one level and its children.

W depends on the shape. A tree where every node has one child has W = 1. A complete binary tree has about N / 2 nodes in its last level, so W is about N / 2.

A tree has no cycles, so no node is reached twice. A graph can reach one node from two parents. Then add a seen set and mark a node when it is added, not when it is popped. Without it, the graph {0: [1, 2], 1: [3], 2: [3], 3: []} puts node 3 in its level twice. Shortest-Path BFS is the card that uses this rule.

Use deque.popleft() and not list.pop(0). list.pop(0) moves every other item, so a walk over N nodes costs O(N^2) time.

60-Second Pitch

"The output is grouped by level, so I use a queue and process one level per round. At the start of each round, queue holds exactly one level, so I copy len(queue) into level_size. I pop exactly that many nodes, record their values, and add their children to the back. Those children are the next level. I must freeze the size before the loop, because the queue grows while the loop runs. A condition that checks the queue again would run into the next level. Each node is added once and popped once, so the time is O(N). The space is O(W), where W is the widest level. For a graph, I would add a seen set and mark each node when it is added."

Common Questions

Why do you need level_size at all? Why not store a depth with each node?: You can store (node, depth) pairs, and it works. But level_size gives the same boundary with no extra value per node. The queue itself separates the levels, so one integer per round is enough.
What are the time and space complexity of levelOrder?: O(N) time, because each node is added once and popped once with constant work. O(W) space for queue and current_level, where W is the number of nodes in the widest level. W is 1 for a chain and about N / 2 for a complete binary tree. The levels result itself holds N values.
How do you change it for Binary Tree Zigzag Level Order Traversal (LC 103)?: Keep the traversal the same, and reverse current_level on every second level. Use a boolean that flips each round, or the parity of len(levels). The queue order stays left to right, because the children must still be added left first.
Could you solve it with depth-first search instead?: Yes. Call dfs(node, depth), and when depth == len(levels), append a new list. Then add node.val to levels[depth]. It has the same O(N) time. Its space is the recursion depth, which is O(N) for a chain, so a very deep tree can exceed Python's recursion limit. BFS has no recursion.
What changes when the input is a graph and not a tree?: Add a seen set that holds the start nodes, and add a neighbour to queue only if it is not in seen. Mark it when you add it, not when you pop it. Then each node is added once, and the levels are the distances from the start. That is the idea of Shortest-Path BFS.

SWE Reasoning

Spot it

The answer is grouped by depth: one list per level, one value per level, or the nodes on one side of the tree.
The wording names levels, rows, layers, depth, "left to right" or "zigzag".
A depth-first search would need a depth argument and a list of lists indexed by depth. Level order BFS avoids that bookkeeping.
Each level can be processed with a pass over the nodes of that level, such as a sum, a maximum, a last element or a reversal.
The input is a tree, so there is no cycle. If it is a graph, you need a seen set as well.

The invariant, step by step

queue starts with the root. Before the loop, it holds exactly level 0.
A round begins with level_size = len(queue). At this moment queue holds one whole level and nothing else, so level_size is the size of that level.
The inner loop pops exactly level_size nodes from the front. Each popped node is added to current_level.
Each popped node adds its existing children to the back. They belong to the next level, and they stay behind the nodes that are still waiting in this level.
When the inner loop ends, all nodes of the level were popped and none of the next level was touched. current_level is the full level, so levels.append(current_level) records it.
Now queue holds exactly the next level. The invariant is true again, so the next round starts correctly. The loop ends when a level adds no children and queue is empty.

Traps

while queue inside the round. The queue grows during the round, so the loop does not stop at the level boundary. Every node ends up in one list. Use for _ in range(level_size).
level_size read after children are added. The size then includes some of the next level. Read it once at the start of the round.
queue[-1] read after the round. It is the last node of the next level, or an IndexError after the last level. Read it before the inner loop.
No seen set on a graph. A node with two parents is added twice and appears twice in its level. Mark each node when you add it.
list.pop(0). The answer is correct, but each pop costs O(N), so the walk costs O(N^2). Use deque.popleft().
Empty tree. deque([None]) would put None in the queue. Return [] first when root is empty.

Practice

Canonical LeetCode:Binary Tree Level Order Traversal (LC 102)Binary Tree Zigzag Level Order Traversal (LC 103)Deepest Leaves Sum (LC 1302)Binary Tree Right Side View (LC 199)Average of Levels in Binary Tree (LC 637)Find Largest Value in Each Tree Row (LC 515)Maximum Level Sum of a Binary Tree (LC 1161)

Theory Context•Breadth-First Search (BFS)

P0EasyMental model~6 min speedrun

Level Order Traversal (BFS by Level)

Grows into

Topological Sort Multi-Source BFS Graph BFS

Unlocks

Shortest-Path BFS

The problem

Binary Tree Level Order Traversal (LC 102)(opens leetcode.com)

Example 1

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

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

Depth 0 holds 3, depth 1 holds 9 and 20, depth 2 holds 15 and 7.

Level-Order BFS

root ➔ freeze level_size = len(queue) ➔ batch process ring

Spot it when: The output is grouped by depth: one list per level, zigzag order, the rightmost node or the sum of each level.

Level-Order BFS

Python

1	from collections import deque
2	from typing import Callable, Iterable, List, Optional, TypeVar
3
4	Item = TypeVar("Item")
5
6	class TreeNode:
7	def __init__(self, val: int = 0, left: Optional["TreeNode"] = None, right: Optional["TreeNode"] = None):
8	self.val = val
9	self.left = left
10	self.right = right
11
12
13	def level_by_level(start: Iterable[Item], children: Callable[[Item], Iterable[Item]], record: Callable[[List[Item]], None]) -> None:
14	"""Level-Order BFS: hand the nodes of each level, left to right, to record(level), level after level.
15	start is the first level. children(node) lists the nodes of the next level below node.
16	Precondition: every node is reached once, as in a tree, or children skips the nodes already seen.
17	V = the nodes. W = the largest level. T = the cost of one children call, or of record for one node.
18	Time: O(V * T) \| Space: O(W) queue and current level
19	"""
20	queue = deque(start) # holds nodes queued for this or a later level, in enqueue order
21
22	while queue:
23	# 1. Snapshot the Level Boundary:
24	# len(queue) right now counts only nodes queued from the previous level, so
25	# freezing it before the inner loop keeps this level's own children out of
26	# the current sweep.
27	level_size = len(queue)
28	current_level = []
29
30	for _ in range(level_size):
31	# 2. Pop and Record This Level's Node:
32	# popleft() returns nodes in the order they were queued, so the
33	# earliest-queued node is always processed first.
34	node = queue.popleft()
35	current_level.append(node)
36	queue.extend(children(node))
37
38	# 3. Record the Completed Level:
39	record(current_level)

Invariant: At the start of each round, queue holds exactly the nodes of one level, left to right, and level_size is their count.

See it run

Level-Order BFS on root = [3, 9, 20, null, null, 15, 7], step by step

level_size 0len(queue) 1current_level []levels []

Each column is one node, in the order it is added to queue. The top row is queue. The bottom row shows a node's value once it is popped.

node the node popped now
in level a node of this level that is waiting
queued a node just added to the queue
level a node of the level that was just recorded

queue = deque([root]) holds the root 3. It is level 0.

queue

3queued

popped

1 / 16

Gotchas1 of 4

The trap
Gotcha 1: Looping while queue inside the round
Mistake
```
while queue:
```
Fix
```
for _ in range(level_size):
```
What happens: Children are added to the back of queue during the round. while queue keeps popping them in the same round. So the loop runs on into the next level, and every node ends up in one list. level_size = len(queue) is read once, before any child is added. The inner loop runs exactly that many times.
Example: Binary Tree Level Order Traversal (LC 102): root = [3,9,20,null,null,15,7]
Mistake: returns [[3, 9, 20, 15, 7]]Fix: returns [[3], [9, 20], [15, 7]]
Gotcha 2: Reading queue[-1] after the round instead of before it
Mistake
```
for _ in range(level_size):
    ...
view.append(queue[-1].val)
```
Fix
```
view.append(queue[-1].val)
for _ in range(level_size):
    ...
```
What happens: Binary Tree Right Side View (LC 199) keeps the last node of each level. Before the round, queue[-1] is that node. After the round, the queue holds the next level, so queue[-1] is the next level's last node. After the last level the queue is empty, and queue[-1] raises an IndexError.
Example: root = [1,2,3,null,5,null,4]
Mistake: raises IndexErrorFix: returns [1, 3, 4]
Gotcha 3: Running it on a graph without a seen set
Mistake
```
queue.append(nxt)
```
Fix
```
if nxt not in seen:
    seen.add(nxt)
    queue.append(nxt)
```
What happens: In a tree, each node has one parent, so it is added once. In a graph, two nodes can both point to the same node. Without seen, that node is added once per edge into it. In the example, node 3 appears twice in its level. Mark each node when you add it, as in Shortest-Path BFS.
Example: adj = {0: [1, 2], 1: [3], 2: [3], 3: []}, start = 0
Mistake: returns [[0], [1, 2], [3, 3]]Fix: returns [[0], [1, 2], [3]]
Gotcha 4: Using list.pop(0) instead of deque.popleft()
Mistake
```
node = queue.pop(0)
```
Fix
```
node = queue.popleft()
```
What happens: list.pop(0) moves every other item one place to the left, so it costs O(n) time. BFS pops every node once, so the whole walk costs O(n^2) time. collections.deque removes from the front in O(1) time. The answer is the same, only slower.

Not this one if…

You need the length of the shortest route to one target cell, as in Shortest Path in Binary Matrix (LC 1091), not the nodes grouped by level. See Shortest-Path BFS

Deep Dive

Why `level_size` marks the level boundary

The trap: the queue grows during the round

Where to read the level: before, during or after the round

Each problem on the card asks for one value per level. Where you read it decides the answer.

Deepest Leaves Sum (LC 1302) keeps only the last current_level, because the last level that is recorded is the deepest one.

The cost, and what changes on a graph

W depends on the shape. A tree where every node has one child has W = 1. A complete binary tree has about N / 2 nodes in its last level, so W is about N / 2.

Use deque.popleft() and not list.pop(0). list.pop(0) moves every other item, so a walk over N nodes costs O(N^2) time.

60-Second Pitch

Common Questions

Why do you need level_size at all? Why not store a depth with each node?: You can store (node, depth) pairs, and it works. But level_size gives the same boundary with no extra value per node. The queue itself separates the levels, so one integer per round is enough.
What are the time and space complexity of levelOrder?: O(N) time, because each node is added once and popped once with constant work. O(W) space for queue and current_level, where W is the number of nodes in the widest level. W is 1 for a chain and about N / 2 for a complete binary tree. The levels result itself holds N values.
How do you change it for Binary Tree Zigzag Level Order Traversal (LC 103)?: Keep the traversal the same, and reverse current_level on every second level. Use a boolean that flips each round, or the parity of len(levels). The queue order stays left to right, because the children must still be added left first.
Could you solve it with depth-first search instead?: Yes. Call dfs(node, depth), and when depth == len(levels), append a new list. Then add node.val to levels[depth]. It has the same O(N) time. Its space is the recursion depth, which is O(N) for a chain, so a very deep tree can exceed Python's recursion limit. BFS has no recursion.
What changes when the input is a graph and not a tree?: Add a seen set that holds the start nodes, and add a neighbour to queue only if it is not in seen. Mark it when you add it, not when you pop it. Then each node is added once, and the levels are the distances from the start. That is the idea of Shortest-Path BFS.

SWE Reasoning

Spot it

The answer is grouped by depth: one list per level, one value per level, or the nodes on one side of the tree.
The wording names levels, rows, layers, depth, "left to right" or "zigzag".
A depth-first search would need a depth argument and a list of lists indexed by depth. Level order BFS avoids that bookkeeping.
Each level can be processed with a pass over the nodes of that level, such as a sum, a maximum, a last element or a reversal.
The input is a tree, so there is no cycle. If it is a graph, you need a seen set as well.

The invariant, step by step

queue starts with the root. Before the loop, it holds exactly level 0.
A round begins with level_size = len(queue). At this moment queue holds one whole level and nothing else, so level_size is the size of that level.
The inner loop pops exactly level_size nodes from the front. Each popped node is added to current_level.
Each popped node adds its existing children to the back. They belong to the next level, and they stay behind the nodes that are still waiting in this level.
When the inner loop ends, all nodes of the level were popped and none of the next level was touched. current_level is the full level, so levels.append(current_level) records it.
Now queue holds exactly the next level. The invariant is true again, so the next round starts correctly. The loop ends when a level adds no children and queue is empty.

Traps

while queue inside the round. The queue grows during the round, so the loop does not stop at the level boundary. Every node ends up in one list. Use for _ in range(level_size).
level_size read after children are added. The size then includes some of the next level. Read it once at the start of the round.
queue[-1] read after the round. It is the last node of the next level, or an IndexError after the last level. Read it before the inner loop.
No seen set on a graph. A node with two parents is added twice and appears twice in its level. Mark each node when you add it.
list.pop(0). The answer is correct, but each pop costs O(N), so the walk costs O(N^2). Use deque.popleft().
Empty tree. deque([None]) would put None in the queue. Return [] first when root is empty.

Practice

Theory Context•Breadth-First Search (BFS)

P0EasyMental model~6 min speedrun

Level Order Traversal (BFS by Level)

Grows into

Topological Sort Multi-Source BFS Graph BFS

Unlocks

Shortest-Path BFS

The problem

Binary Tree Level Order Traversal (LC 102)(opens leetcode.com)

Example 1

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

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

Depth 0 holds 3, depth 1 holds 9 and 20, depth 2 holds 15 and 7.

Level-Order BFS

root ➔ freeze level_size = len(queue) ➔ batch process ring

Spot it when: The output is grouped by depth: one list per level, zigzag order, the rightmost node or the sum of each level.

Level-Order BFS

Python

1	from collections import deque
2	from typing import Callable, Iterable, List, Optional, TypeVar
3
4	Item = TypeVar("Item")
5
6	class TreeNode:
7	def __init__(self, val: int = 0, left: Optional["TreeNode"] = None, right: Optional["TreeNode"] = None):
8	self.val = val
9	self.left = left
10	self.right = right
11
12
13	def level_by_level(start: Iterable[Item], children: Callable[[Item], Iterable[Item]], record: Callable[[List[Item]], None]) -> None:
14	"""Level-Order BFS: hand the nodes of each level, left to right, to record(level), level after level.
15	start is the first level. children(node) lists the nodes of the next level below node.
16	Precondition: every node is reached once, as in a tree, or children skips the nodes already seen.
17	V = the nodes. W = the largest level. T = the cost of one children call, or of record for one node.
18	Time: O(V * T) \| Space: O(W) queue and current level
19	"""
20	queue = deque(start) # holds nodes queued for this or a later level, in enqueue order
21
22	while queue:
23	# 1. Snapshot the Level Boundary:
24	# len(queue) right now counts only nodes queued from the previous level, so
25	# freezing it before the inner loop keeps this level's own children out of
26	# the current sweep.
27	level_size = len(queue)
28	current_level = []
29
30	for _ in range(level_size):
31	# 2. Pop and Record This Level's Node:
32	# popleft() returns nodes in the order they were queued, so the
33	# earliest-queued node is always processed first.
34	node = queue.popleft()
35	current_level.append(node)
36	queue.extend(children(node))
37
38	# 3. Record the Completed Level:
39	record(current_level)

Invariant: At the start of each round, queue holds exactly the nodes of one level, left to right, and level_size is their count.

See it run

Level-Order BFS on root = [3, 9, 20, null, null, 15, 7], step by step

level_size 0len(queue) 1current_level []levels []

Each column is one node, in the order it is added to queue. The top row is queue. The bottom row shows a node's value once it is popped.

node the node popped now
in level a node of this level that is waiting
queued a node just added to the queue
level a node of the level that was just recorded

queue = deque([root]) holds the root 3. It is level 0.

queue

3queued

popped

1 / 16

Gotchas1 of 4

The trap
Gotcha 1: Looping while queue inside the round
Mistake
```
while queue:
```
Fix
```
for _ in range(level_size):
```
What happens: Children are added to the back of queue during the round. while queue keeps popping them in the same round. So the loop runs on into the next level, and every node ends up in one list. level_size = len(queue) is read once, before any child is added. The inner loop runs exactly that many times.
Example: Binary Tree Level Order Traversal (LC 102): root = [3,9,20,null,null,15,7]
Mistake: returns [[3, 9, 20, 15, 7]]Fix: returns [[3], [9, 20], [15, 7]]
Gotcha 2: Reading queue[-1] after the round instead of before it
Mistake
```
for _ in range(level_size):
    ...
view.append(queue[-1].val)
```
Fix
```
view.append(queue[-1].val)
for _ in range(level_size):
    ...
```
What happens: Binary Tree Right Side View (LC 199) keeps the last node of each level. Before the round, queue[-1] is that node. After the round, the queue holds the next level, so queue[-1] is the next level's last node. After the last level the queue is empty, and queue[-1] raises an IndexError.
Example: root = [1,2,3,null,5,null,4]
Mistake: raises IndexErrorFix: returns [1, 3, 4]
Gotcha 3: Running it on a graph without a seen set
Mistake
```
queue.append(nxt)
```
Fix
```
if nxt not in seen:
    seen.add(nxt)
    queue.append(nxt)
```
What happens: In a tree, each node has one parent, so it is added once. In a graph, two nodes can both point to the same node. Without seen, that node is added once per edge into it. In the example, node 3 appears twice in its level. Mark each node when you add it, as in Shortest-Path BFS.
Example: adj = {0: [1, 2], 1: [3], 2: [3], 3: []}, start = 0
Mistake: returns [[0], [1, 2], [3, 3]]Fix: returns [[0], [1, 2], [3]]
Gotcha 4: Using list.pop(0) instead of deque.popleft()
Mistake
```
node = queue.pop(0)
```
Fix
```
node = queue.popleft()
```
What happens: list.pop(0) moves every other item one place to the left, so it costs O(n) time. BFS pops every node once, so the whole walk costs O(n^2) time. collections.deque removes from the front in O(1) time. The answer is the same, only slower.

Not this one if…

You need the length of the shortest route to one target cell, as in Shortest Path in Binary Matrix (LC 1091), not the nodes grouped by level. See Shortest-Path BFS

Deep Dive

Why `level_size` marks the level boundary

The trap: the queue grows during the round

Where to read the level: before, during or after the round

Each problem on the card asks for one value per level. Where you read it decides the answer.

Deepest Leaves Sum (LC 1302) keeps only the last current_level, because the last level that is recorded is the deepest one.

The cost, and what changes on a graph

W depends on the shape. A tree where every node has one child has W = 1. A complete binary tree has about N / 2 nodes in its last level, so W is about N / 2.

Use deque.popleft() and not list.pop(0). list.pop(0) moves every other item, so a walk over N nodes costs O(N^2) time.

60-Second Pitch

Common Questions

Why do you need level_size at all? Why not store a depth with each node?: You can store (node, depth) pairs, and it works. But level_size gives the same boundary with no extra value per node. The queue itself separates the levels, so one integer per round is enough.
What are the time and space complexity of levelOrder?: O(N) time, because each node is added once and popped once with constant work. O(W) space for queue and current_level, where W is the number of nodes in the widest level. W is 1 for a chain and about N / 2 for a complete binary tree. The levels result itself holds N values.
How do you change it for Binary Tree Zigzag Level Order Traversal (LC 103)?: Keep the traversal the same, and reverse current_level on every second level. Use a boolean that flips each round, or the parity of len(levels). The queue order stays left to right, because the children must still be added left first.
Could you solve it with depth-first search instead?: Yes. Call dfs(node, depth), and when depth == len(levels), append a new list. Then add node.val to levels[depth]. It has the same O(N) time. Its space is the recursion depth, which is O(N) for a chain, so a very deep tree can exceed Python's recursion limit. BFS has no recursion.
What changes when the input is a graph and not a tree?: Add a seen set that holds the start nodes, and add a neighbour to queue only if it is not in seen. Mark it when you add it, not when you pop it. Then each node is added once, and the levels are the distances from the start. That is the idea of Shortest-Path BFS.

SWE Reasoning

Spot it

The answer is grouped by depth: one list per level, one value per level, or the nodes on one side of the tree.
The wording names levels, rows, layers, depth, "left to right" or "zigzag".
A depth-first search would need a depth argument and a list of lists indexed by depth. Level order BFS avoids that bookkeeping.
Each level can be processed with a pass over the nodes of that level, such as a sum, a maximum, a last element or a reversal.
The input is a tree, so there is no cycle. If it is a graph, you need a seen set as well.

The invariant, step by step

queue starts with the root. Before the loop, it holds exactly level 0.
A round begins with level_size = len(queue). At this moment queue holds one whole level and nothing else, so level_size is the size of that level.
The inner loop pops exactly level_size nodes from the front. Each popped node is added to current_level.
Each popped node adds its existing children to the back. They belong to the next level, and they stay behind the nodes that are still waiting in this level.
When the inner loop ends, all nodes of the level were popped and none of the next level was touched. current_level is the full level, so levels.append(current_level) records it.
Now queue holds exactly the next level. The invariant is true again, so the next round starts correctly. The loop ends when a level adds no children and queue is empty.

Traps

while queue inside the round. The queue grows during the round, so the loop does not stop at the level boundary. Every node ends up in one list. Use for _ in range(level_size).
level_size read after children are added. The size then includes some of the next level. Read it once at the start of the round.
queue[-1] read after the round. It is the last node of the next level, or an IndexError after the last level. Read it before the inner loop.
No seen set on a graph. A node with two parents is added twice and appears twice in its level. Mark each node when you add it.
list.pop(0). The answer is correct, but each pop costs O(N), so the walk costs O(N^2). Use deque.popleft().
Empty tree. deque([None]) would put None in the queue. Return [] first when root is empty.

Practice

Theory Context•Breadth-First Search (BFS)

P0EasyMental model~6 min speedrun

Level Order Traversal (BFS by Level)

Grows into

Topological Sort Multi-Source BFS Graph BFS

Unlocks

Shortest-Path BFS

The problem

Binary Tree Level Order Traversal (LC 102)(opens leetcode.com)

Example 1

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

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

Depth 0 holds 3, depth 1 holds 9 and 20, depth 2 holds 15 and 7.

Level-Order BFS

root ➔ freeze level_size = len(queue) ➔ batch process ring

Spot it when: The output is grouped by depth: one list per level, zigzag order, the rightmost node or the sum of each level.

Level-Order BFS

Python

1	from collections import deque
2	from typing import Callable, Iterable, List, Optional, TypeVar
3
4	Item = TypeVar("Item")
5
6	class TreeNode:
7	def __init__(self, val: int = 0, left: Optional["TreeNode"] = None, right: Optional["TreeNode"] = None):
8	self.val = val
9	self.left = left
10	self.right = right
11
12
13	def level_by_level(start: Iterable[Item], children: Callable[[Item], Iterable[Item]], record: Callable[[List[Item]], None]) -> None:
14	"""Level-Order BFS: hand the nodes of each level, left to right, to record(level), level after level.
15	start is the first level. children(node) lists the nodes of the next level below node.
16	Precondition: every node is reached once, as in a tree, or children skips the nodes already seen.
17	V = the nodes. W = the largest level. T = the cost of one children call, or of record for one node.
18	Time: O(V * T) \| Space: O(W) queue and current level
19	"""
20	queue = deque(start) # holds nodes queued for this or a later level, in enqueue order
21
22	while queue:
23	# 1. Snapshot the Level Boundary:
24	# len(queue) right now counts only nodes queued from the previous level, so
25	# freezing it before the inner loop keeps this level's own children out of
26	# the current sweep.
27	level_size = len(queue)
28	current_level = []
29
30	for _ in range(level_size):
31	# 2. Pop and Record This Level's Node:
32	# popleft() returns nodes in the order they were queued, so the
33	# earliest-queued node is always processed first.
34	node = queue.popleft()
35	current_level.append(node)
36	queue.extend(children(node))
37
38	# 3. Record the Completed Level:
39	record(current_level)

Invariant: At the start of each round, queue holds exactly the nodes of one level, left to right, and level_size is their count.

See it run

Level-Order BFS on root = [3, 9, 20, null, null, 15, 7], step by step

level_size 0len(queue) 1current_level []levels []

Each column is one node, in the order it is added to queue. The top row is queue. The bottom row shows a node's value once it is popped.

node the node popped now
in level a node of this level that is waiting
queued a node just added to the queue
level a node of the level that was just recorded

queue = deque([root]) holds the root 3. It is level 0.

queue

3queued

popped

1 / 16

Gotchas1 of 4

The trap
Gotcha 1: Looping while queue inside the round
Mistake
```
while queue:
```
Fix
```
for _ in range(level_size):
```
What happens: Children are added to the back of queue during the round. while queue keeps popping them in the same round. So the loop runs on into the next level, and every node ends up in one list. level_size = len(queue) is read once, before any child is added. The inner loop runs exactly that many times.
Example: Binary Tree Level Order Traversal (LC 102): root = [3,9,20,null,null,15,7]
Mistake: returns [[3, 9, 20, 15, 7]]Fix: returns [[3], [9, 20], [15, 7]]
Gotcha 2: Reading queue[-1] after the round instead of before it
Mistake
```
for _ in range(level_size):
    ...
view.append(queue[-1].val)
```
Fix
```
view.append(queue[-1].val)
for _ in range(level_size):
    ...
```
What happens: Binary Tree Right Side View (LC 199) keeps the last node of each level. Before the round, queue[-1] is that node. After the round, the queue holds the next level, so queue[-1] is the next level's last node. After the last level the queue is empty, and queue[-1] raises an IndexError.
Example: root = [1,2,3,null,5,null,4]
Mistake: raises IndexErrorFix: returns [1, 3, 4]
Gotcha 3: Running it on a graph without a seen set
Mistake
```
queue.append(nxt)
```
Fix
```
if nxt not in seen:
    seen.add(nxt)
    queue.append(nxt)
```
What happens: In a tree, each node has one parent, so it is added once. In a graph, two nodes can both point to the same node. Without seen, that node is added once per edge into it. In the example, node 3 appears twice in its level. Mark each node when you add it, as in Shortest-Path BFS.
Example: adj = {0: [1, 2], 1: [3], 2: [3], 3: []}, start = 0
Mistake: returns [[0], [1, 2], [3, 3]]Fix: returns [[0], [1, 2], [3]]
Gotcha 4: Using list.pop(0) instead of deque.popleft()
Mistake
```
node = queue.pop(0)
```
Fix
```
node = queue.popleft()
```
What happens: list.pop(0) moves every other item one place to the left, so it costs O(n) time. BFS pops every node once, so the whole walk costs O(n^2) time. collections.deque removes from the front in O(1) time. The answer is the same, only slower.

Not this one if…

You need the length of the shortest route to one target cell, as in Shortest Path in Binary Matrix (LC 1091), not the nodes grouped by level. See Shortest-Path BFS

Deep Dive

Why `level_size` marks the level boundary

The trap: the queue grows during the round

Where to read the level: before, during or after the round

Each problem on the card asks for one value per level. Where you read it decides the answer.

Deepest Leaves Sum (LC 1302) keeps only the last current_level, because the last level that is recorded is the deepest one.

The cost, and what changes on a graph

W depends on the shape. A tree where every node has one child has W = 1. A complete binary tree has about N / 2 nodes in its last level, so W is about N / 2.

Use deque.popleft() and not list.pop(0). list.pop(0) moves every other item, so a walk over N nodes costs O(N^2) time.

60-Second Pitch

Common Questions

Why do you need level_size at all? Why not store a depth with each node?: You can store (node, depth) pairs, and it works. But level_size gives the same boundary with no extra value per node. The queue itself separates the levels, so one integer per round is enough.
What are the time and space complexity of levelOrder?: O(N) time, because each node is added once and popped once with constant work. O(W) space for queue and current_level, where W is the number of nodes in the widest level. W is 1 for a chain and about N / 2 for a complete binary tree. The levels result itself holds N values.
How do you change it for Binary Tree Zigzag Level Order Traversal (LC 103)?: Keep the traversal the same, and reverse current_level on every second level. Use a boolean that flips each round, or the parity of len(levels). The queue order stays left to right, because the children must still be added left first.
Could you solve it with depth-first search instead?: Yes. Call dfs(node, depth), and when depth == len(levels), append a new list. Then add node.val to levels[depth]. It has the same O(N) time. Its space is the recursion depth, which is O(N) for a chain, so a very deep tree can exceed Python's recursion limit. BFS has no recursion.
What changes when the input is a graph and not a tree?: Add a seen set that holds the start nodes, and add a neighbour to queue only if it is not in seen. Mark it when you add it, not when you pop it. Then each node is added once, and the levels are the distances from the start. That is the idea of Shortest-Path BFS.

SWE Reasoning

Spot it

The answer is grouped by depth: one list per level, one value per level, or the nodes on one side of the tree.
The wording names levels, rows, layers, depth, "left to right" or "zigzag".
A depth-first search would need a depth argument and a list of lists indexed by depth. Level order BFS avoids that bookkeeping.
Each level can be processed with a pass over the nodes of that level, such as a sum, a maximum, a last element or a reversal.
The input is a tree, so there is no cycle. If it is a graph, you need a seen set as well.

The invariant, step by step

queue starts with the root. Before the loop, it holds exactly level 0.
A round begins with level_size = len(queue). At this moment queue holds one whole level and nothing else, so level_size is the size of that level.
The inner loop pops exactly level_size nodes from the front. Each popped node is added to current_level.
Each popped node adds its existing children to the back. They belong to the next level, and they stay behind the nodes that are still waiting in this level.
When the inner loop ends, all nodes of the level were popped and none of the next level was touched. current_level is the full level, so levels.append(current_level) records it.
Now queue holds exactly the next level. The invariant is true again, so the next round starts correctly. The loop ends when a level adds no children and queue is empty.

Traps

while queue inside the round. The queue grows during the round, so the loop does not stop at the level boundary. Every node ends up in one list. Use for _ in range(level_size).
level_size read after children are added. The size then includes some of the next level. Read it once at the start of the round.
queue[-1] read after the round. It is the last node of the next level, or an IndexError after the last level. Read it before the inner loop.
No seen set on a graph. A node with two parents is added twice and appears twice in its level. Mark each node when you add it.
list.pop(0). The answer is correct, but each pop costs O(N), so the walk costs O(N^2). Use deque.popleft().
Empty tree. deque([None]) would put None in the queue. Return [] first when root is empty.

Binary Tree Level Order Traversal (LC 102)(opens leetcode.com)

Level-Order BFS

See it run

Deep Dive

Why level_size marks the level boundary

The trap: the queue grows during the round

Where to read the level: before, during or after the round

The cost, and what changes on a graph

60-Second Pitch

Common Questions

SWE Reasoning

Spot it

The invariant, step by step

Traps

Practice

Binary Tree Level Order Traversal (LC 102)(opens leetcode.com)

Level-Order BFS

See it run

Deep Dive

Why level_size marks the level boundary

The trap: the queue grows during the round

Where to read the level: before, during or after the round

The cost, and what changes on a graph

60-Second Pitch

Common Questions

SWE Reasoning

Spot it

The invariant, step by step

Traps

Practice

Binary Tree Level Order Traversal (LC 102)(opens leetcode.com)

Level-Order BFS

See it run

Deep Dive

Why level_size marks the level boundary

The trap: the queue grows during the round

Where to read the level: before, during or after the round

The cost, and what changes on a graph

60-Second Pitch

Common Questions

SWE Reasoning

Spot it

The invariant, step by step

Traps

Practice

Binary Tree Level Order Traversal (LC 102)(opens leetcode.com)

Level-Order BFS

See it run

Deep Dive

Why level_size marks the level boundary

The trap: the queue grows during the round

Where to read the level: before, during or after the round

The cost, and what changes on a graph

60-Second Pitch

Common Questions

SWE Reasoning

Spot it

The invariant, step by step

Traps

Practice

Why `level_size` marks the level boundary

Why `level_size` marks the level boundary

Why `level_size` marks the level boundary

Why `level_size` marks the level boundary