A Queue<T>, a visited set, and one loop that handles a whole level at a time. The first time BFS reaches a node, it got there by the shortest route.
BFS answers two questions that look different. One is process this tree level by level. The other is find the fewest steps from A to B. Both come from one fact. A queue explores nodes in order of their distance from the start.
C# has no built-in deque. You do not need one here. BFS only adds at the back and removes at the front, and Queue<T> does both in O(1). It is a ring buffer over an array, so it is also cache friendly. The Python version of this page is here.
Queue<T>.StackOverflowException.d leaves before any node at distance d + 1. The first time a node is reached, it is reached along a shortest path. It never needs a second visit.Reading the figure. Each colour is one level of the tree. The boxes on the right show the queue when each round starts. Blue is round 1, amber is round 2, and green is round 3. Notice that each box holds exactly one level. So queue.Count at that moment is the width of the level.
int size = queue.Count before the inner loop, and dequeue exactly that many. Everything enqueued during the inner loop belongs to the next level. It waits for the next round. This one line turns a flat traversal into a level-grouped one.// One outer pass per level. Invariant: at the top, the queue holds exactly
// one whole level and nothing else.
while (queue.Count > 0) // > 0: stop when nothing is left to visit
{
int size = queue.Count; // snapshot BEFORE the inner loop
for (int i = 0; i < size; i++) // pop exactly size nodes: this level only
{
var node = queue.Dequeue(); // Dequeue: oldest first, so FIFO order
// ... enqueue children. They land after the snapshot boundary.
}
}
for (int i = 0; i < queue.Count; i++) as the inner loop. This is the C# trap. A for condition is checked again on every pass. So queue.Count is read again after each child is enqueued, and the loop runs into the next level. Python's range(len(queue)) is safe because it reads the length once. In C# you must copy Count into a local first./// <summary>A binary tree node. One shared type for every block on this page.</summary>
/// <param name="val">The value stored in the node.</param>
/// <param name="left">Left child, or null.</param>
/// <param name="right">Right child, or null.</param>
public sealed class TreeNode(int val = 0, TreeNode? left = null, TreeNode? right = null)
{
public int Val = val; // 0 by default: a value when none is given
public TreeNode? Left = left; // null by default: no left child
public TreeNode? Right = right; // null by default: no right child
}
A primary constructor keeps the node to three lines. The fields stay mutable, so tests and tree builders can wire children later.
public static class LevelTemplate
{
/// <summary>Group a tree's values by depth.</summary>
/// <param name="root">Root node, or null for an empty tree.</param>
/// <returns>One list per level, top to bottom, each left to right.</returns>
/// <example><c>ByLevel(new TreeNode(1, new TreeNode(2)))</c>
/// returns <c>[[1], [2]]</c>.</example>
public static List<List<int>> ByLevel(TreeNode? root)
{
var levels = new List<List<int>>();
if (root is null)
return levels; // empty tree: no levels at all
// [root]: a collection expression seeds the queue with level 0.
var queue = new Queue<TreeNode>([root]);
// Invariant: at the top of each pass, the queue holds one whole level.
while (queue.Count > 0) // > 0: stop when nothing is left
{
int size = queue.Count; // snapshot: this level's width
var level = new List<int>(size); // size: exact capacity, no regrowth
// i counts nodes taken from this level. Invariant: i < size.
for (int i = 0; i < size; i++) // 0 to size - 1: this level only
{
TreeNode node = queue.Dequeue(); // Dequeue: oldest first (FIFO)
level.Add(node.Val);
// Children go to the back. They form the next level.
if (node.Left is not null) queue.Enqueue(node.Left);
if (node.Right is not null) queue.Enqueue(node.Right);
}
levels.Add(level);
}
return levels;
}
}
A tree needs no visited set, because there is exactly one path to every node. A graph always does.
public static class StepsTemplate
{
/// <summary>Fewest edges from start to goal, or -1 if goal is unreachable.</summary>
/// <typeparam name="TNode">Node type. It needs value equality, such as int,
/// string, or a (row, col) tuple.</typeparam>
/// <param name="start">Where the search begins.</param>
/// <param name="goal">The node to reach.</param>
/// <param name="neighbours">Returns the nodes one edge away from a node.</param>
/// <returns>The edge count of a shortest path, or -1.</returns>
/// <example><c>ShortestSteps(1, 10, n => [n + 1, n * 2])</c> returns <c>4</c>.</example>
public static int ShortestSteps<TNode>(
TNode start, TNode goal, Func<TNode, IEnumerable<TNode>> neighbours)
where TNode : notnull
{
var queue = new Queue<TNode>([start]);
var seen = new HashSet<TNode> { start }; // start is reached before any step
int steps = 0; // 0: start is 0 edges from itself
// Invariant: the queue holds every node exactly `steps` edges from start.
while (queue.Count > 0) // > 0: nodes still to explore
{
int size = queue.Count; // size: just this distance ring
for (int i = 0; i < size; i++) // i: nodes taken from this ring
{
TNode node = queue.Dequeue();
// BFS reaches nodes in distance order, so the first hit is shortest.
if (EqualityComparer<TNode>.Default.Equals(node, goal))
return steps;
foreach (TNode next in neighbours(node))
{
// Add returns false if already seen. Mark on PUSH, not on pop.
if (seen.Add(next))
queue.Enqueue(next);
}
}
steps++; // + 1: the next ring is one edge farther
}
return -1; // -1: queue ran dry, goal not reachable
}
}
HashSet<T>.Add returns bool. One call both tests and marks, so the seen check costs a single hash.
Reading the figure. Numbers are the step count from S. Blue cells were dequeued in earlier rounds. Amber cells are in the queue now. Green is the goal. Notice that the queue holds only one ring. Every cell at distance 3 leaves the queue before any cell at distance 4 is seen.
List<T> as a queue. list.RemoveAt(0) shifts every element, so it is O(n). That makes the whole BFS O(n²). Use Queue<T>.queue.Count in the inner for. See the warning above. Snapshot it into a local.0. A badly placed goal test returns 1.Return the values of a binary tree grouped by level, from left to right, top to bottom.
public static class LevelOrderTraversal
{
/// <summary>Values of a binary tree, grouped by depth.</summary>
/// <param name="root">Root node, or null.</param>
/// <returns>One list per level, top to bottom, each left to right.</returns>
/// <example>Tree 3 / (9, 20) / (15, 7 under 20) gives <c>[[3], [9, 20], [15, 7]]</c>.</example>
public static List<List<int>> LevelOrder(TreeNode? root)
{
var levels = new List<List<int>>();
if (root is null)
return levels; // empty tree: [] and not [[]]
var queue = new Queue<TreeNode>([root]); // level 0 is just the root
// Invariant: at the top of each pass, the queue holds one whole level.
while (queue.Count > 0) // > 0: some level is still waiting
{
// Count here is exactly the width of the current level.
int size = queue.Count;
var level = new List<int>(size); // size: exact capacity for this level
// i counts nodes taken so far. Children pushed now wait for next round.
for (int i = 0; i < size; i++)
{
TreeNode node = queue.Dequeue(); // Dequeue: oldest first (FIFO)
level.Add(node.Val);
// Left before right keeps each level in left-to-right order.
if (node.Left is not null) queue.Enqueue(node.Left);
if (node.Right is not null) queue.Enqueue(node.Right);
}
levels.Add(level);
}
return levels;
}
}
Reading the figure. Amber boxes are the queue when a round starts. That count is size. Blue boxes are the children enqueued during the round, which are the next level. Green text is the list the round adds to levels. Each blue row becomes the next amber row.
Each node is enqueued and dequeued exactly once. The queue holds at most one level plus part of the next. So its peak is the maximum width. That is O(n) in the worst case and about n/2 for a full tree.
levels.Reverse(). Or levels.Insert(0, level), but that is O(levels) per call.i == size - 1, the last node of each level.long sum, since many int values can overflow. Then add (double)sum / size.Five interview questions, one loop. That is why the template is worth learning exactly.
root is null: returns an empty list, not a list holding one empty list.[[val]].n levels of one node each. The queue never holds more than one node.Same as above, but alternate direction. The first level goes left to right, the second right to left, and so on.
appendleft. C# has no deque, but it does not need one. We know the level width up front, so we allocate an int[size]. Then node i goes to slot i or slot size - 1 - i.bool that flips each round is all the extra state.public static class ZigzagTraversal
{
/// <summary>Level order, alternating left-to-right and right-to-left.</summary>
/// <param name="root">Root node, or null.</param>
/// <returns>One array per level, with odd-numbered levels reversed.</returns>
/// <example>Tree 3 / (9, 20) / (15, 7 under 20) gives <c>[[3], [20, 9], [15, 7]]</c>.</example>
public static List<int[]> ZigzagLevelOrder(TreeNode? root)
{
var levels = new List<int[]>();
if (root is null)
return levels; // empty tree: no levels at all
var queue = new Queue<TreeNode>([root]); // level 0 is just the root
bool leftToRight = true; // level 0 reads left to right
// Invariant: at the top of each pass, the queue holds one whole level,
// and leftToRight says which way to write it.
while (queue.Count > 0) // > 0: some level is still waiting
{
int size = queue.Count; // snapshot: this level's width
var level = new int[size]; // size: one slot per node, filled by index
// i is the visit order inside this level, 0 to size - 1.
for (int i = 0; i < size; i++)
{
TreeNode node = queue.Dequeue();
// size - 1 - i: the mirror slot, so the visit order reverses.
int slot = leftToRight ? i : size - 1 - i;
level[slot] = node.Val;
// The queue itself always goes left then right. Only `level` flips.
if (node.Left is not null) queue.Enqueue(node.Left);
if (node.Right is not null) queue.Enqueue(node.Right);
}
levels.Add(level);
leftToRight = !leftToRight; // flip direction for the next level
}
return levels;
}
}
Reading the figure. Purple arrows show the direction each level is written. The amber level is the one that reads right to left. The boxes on the right are its level array. BFS still dequeues 9 before 20. Node 9 has i = 0, so it goes to the mirror slot size - 1 - 0 = 1. Node 20 goes to slot 0. The level reads [20, 9] with no extra pass.
Right before Left on alternating levels. That gives the right answer on a perfect tree. It gives the wrong one as soon as a node has only one child, because the mirrored order no longer lines up level to level. Keep the traversal standard and change only the output order. Interviewers ask this exact follow-up.Each node is written once, straight into its final slot. A List<int> plus level.Reverse() also works in O(n) total. The array version just skips the second touch. A LinkedList<int> with AddFirst mirrors the Python deque. It allocates a node per value, so the array is the better C# choice.
A grid holds 0 for empty, 1 for a fresh orange, and 2 for a rotten one. Every minute, a rotten orange rots each fresh orange next to it, in the four main directions. Return the minutes until no fresh orange is left, or -1 if that never happens.
-1 case at the end, with no second scan.public static class RottingOranges
{
// Down, up, right, left as (row step, col step). No diagonals.
private static readonly (int Dr, int Dc)[] Directions = [(1, 0), (-1, 0), (0, 1), (0, -1)];
/// <summary>Minutes until every fresh orange rots, or -1 if some never do.</summary>
/// <param name="grid">0 empty, 1 fresh, 2 rotten. Changed in place as rot spreads.</param>
/// <returns>Elapsed minutes, or -1 if a fresh orange is unreachable.</returns>
/// <example><c>OrangesRotting([[2, 1, 1], [1, 1, 0], [0, 1, 1]])</c>
/// returns <c>4</c>.</example>
public static int OrangesRotting(int[][] grid)
{
// grid[0]: the first row. If it is empty, there are no columns.
if (grid.Length == 0 || grid[0].Length == 0)
return 0; // 0: no oranges, so no time passes
int rows = grid.Length, cols = grid[0].Length; // grid[0]: all rows share this width
var queue = new Queue<(int R, int C)>();
int fresh = 0; // 0: count starts empty
// Seed every rotten cell at once: this is a multi-source BFS.
// r, c walk every cell once, row by row.
for (int r = 0; r < rows; r++)
{
for (int c = 0; c < cols; c++)
{
if (grid[r][c] == 2) // 2: rotten, a starting source
queue.Enqueue((r, c));
else if (grid[r][c] == 1) // 1: fresh, must rot before we finish
fresh++; // + 1: one more fresh orange to rot
}
}
if (fresh == 0) // 0 fresh: nothing to rot
return 0; // 0 minutes, even for an all-empty grid
int minutes = 0; // 0: time starts before any spread
// Stop as soon as nothing fresh is left, so we do not count an empty round.
// Invariant: the queue holds exactly the cells that rotted at `minutes`.
while (queue.Count > 0 && fresh > 0) // > 0 twice: a wave exists and work remains
{
int size = queue.Count; // size: one minute's wave only
for (int i = 0; i < size; i++) // i: cells taken from this wave
{
var (r, c) = queue.Dequeue();
foreach (var (dr, dc) in Directions)
{
int nr = r + dr, nc = c + dc;
// 0 <= ... < rows/cols: stay on the grid. == 1: fresh only.
if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr][nc] == 1)
{
grid[nr][nc] = 2; // 2: rotten. Mark on push: grid is the visited set
fresh--; // - 1: one fewer fresh orange left
queue.Enqueue((nr, nc));
}
}
}
minutes++; // + 1: one wave of spread is one minute
}
// fresh == 0: all rotted. Otherwise -1: some orange was walled off.
return fresh == 0 ? minutes : -1;
}
}
[[2,1,1],[1,1,0],[0,1,1]], one rotten orange at the top left and six fresh:
Answer 4.
Reading the figure. Amber cells are the queue for that minute, the oranges that just turned rotten. Blue cells rotted in an earlier minute. White cells are still fresh. Grey cells are empty. Read left to right. Each amber set touches the one before it, and the count under each grid drops to 0 at minute 4.
Every cell is enqueued at most once. The queue peaks at the size of the rot frontier, which is O(rows × cols) in the worst case. Queue<(int R, int C)> stores value tuples inline in its array, so there is no allocation per cell.
queue.Count > 0 && fresh > 0queue.Count > 0, the last round dequeues the final frontier and finds no fresh neighbours. It still adds one to minutes. That over-counts by one. Adding fresh > 0 stops as soon as the job is done. The other fix is to add a minute only when something rotted. Both are fine. Pick one and explain it.2 we write. Say so, and offer to copy first if the caller needs the grid back.0, including for an all-zero grid.fresh > 0, so it returns -1.-1.You get beginWord, endWord, and a dictionary wordList. Find the length of the shortest chain from beginWord to endWord. Each step changes exactly one letter, and every word after the first must be in the dictionary. The length counts words, not steps. Return 0 if no chain exists.
new string(chars) copies L chars.h*t.
With N words of length L, the second option is O(N · 26 · L²) overall.
public static class WordLadder
{
/// <summary>Length of the shortest one-letter-at-a-time word ladder.</summary>
/// <param name="beginWord">Starting word. It need not be in wordList.</param>
/// <param name="endWord">Target word. It must be in wordList or the answer is 0.</param>
/// <param name="wordList">The allowed words after the first.</param>
/// <returns>Words in the shortest ladder, counting both ends, or 0.</returns>
/// <example><c>LadderLength("hit", "cog", ["hot", "dot", "dog", "lot", "log", "cog"])</c>
/// returns <c>5</c>.</example>
public static int LadderLength(string beginWord, string endWord, IEnumerable<string> wordList)
{
var words = new HashSet<string>(wordList); // O(1) lookup, and our visited set
if (!words.Contains(endWord))
return 0; // 0: no ladder can end on a missing word
var queue = new Queue<string>([beginWord]);
words.Remove(beginWord); // Remove is safe if it is absent: returns false
int steps = 1; // 1: the ladder includes beginWord itself
// Invariant: the queue holds every word that is `steps` words into a ladder.
while (queue.Count > 0) // > 0: words still to expand
{
int size = queue.Count; // size: this ladder length only
for (int k = 0; k < size; k++) // k: words taken from this ring
{
string word = queue.Dequeue();
// BFS finds words in ladder-length order, so the first hit is shortest.
if (word == endWord)
return steps;
// Strings are immutable, so edit a char[] copy and restore it after.
char[] chars = word.ToCharArray();
for (int i = 0; i < chars.Length; i++) // i: the position being changed
{
char original = chars[i];
// 'a' to 'z': try all 26 lowercase letters in this position.
for (char letter = 'a'; letter <= 'z'; letter++)
{
if (letter == original)
continue; // same letter: same word, not a neighbour
chars[i] = letter;
var candidate = new string(chars); // O(L) copy
// Remove returns true only if it was there. Mark on push.
if (words.Remove(candidate))
queue.Enqueue(candidate);
}
chars[i] = original; // restore before moving to the next position
}
}
steps++; // + 1: the next ring adds one word
}
return 0; // 0: queue ran dry, no ladder exists
}
}
words is the visited set. A word reached at distance d is never worth reaching again, because any later route is at least as long. Deleting it does two jobs. It stops revisits, and it shrinks the candidate set as the search goes on. That is why no separate seen set appears. HashSet<T>.Remove returns bool, so one call both tests and marks.begin = "hit", end = "cog", dictionary ["hot","dot","dog","lot","log","cog"]:
hit.hot.dot, lot.dog, log.cog. It matches, so return 5.cog is found at the fewest steps.Reading the figure. Each column is one round of BFS, and the label on top is the value of steps. Lines join words that differ by one letter. Green boxes and lines trace one shortest ladder. Blue boxes are reached but not on it. Dashed lines join two words in the same round. BFS never uses them, because the far word is already removed from words.
Most of the 26 · L candidates are not in the dictionary. The version above still builds a string for each one. Since .NET 9, a HashSet<string> can be searched with a ReadOnlySpan<char> through GetAlternateLookup. A miss then allocates nothing. Only a hit hands back the stored string. Mention this if the interviewer asks about allocations or GC pressure.
public static class WordLadderSpan
{
/// <summary>Same answer as WordLadder.LadderLength, without a string per candidate.</summary>
/// <param name="beginWord">Starting word. It need not be in wordList.</param>
/// <param name="endWord">Target word. It must be in wordList or the answer is 0.</param>
/// <param name="wordList">The allowed words after the first.</param>
/// <returns>Words in the shortest ladder, counting both ends, or 0.</returns>
/// <example><c>LadderLength("hit", "cog", ["hot", "dot", "dog", "lot", "log", "cog"])</c>
/// returns <c>5</c>.</example>
public static int LadderLength(string beginWord, string endWord, IEnumerable<string> wordList)
{
var words = new HashSet<string>(wordList);
if (!words.Contains(endWord))
return 0; // 0: no ladder can end on a missing word
// Lets us query the set with a span of chars instead of a string.
var lookup = words.GetAlternateLookup<ReadOnlySpan<char>>();
var queue = new Queue<string>([beginWord]);
words.Remove(beginWord);
int steps = 1; // 1: the ladder includes beginWord itself
// Invariant: the queue holds every word that is `steps` words into a ladder.
while (queue.Count > 0) // > 0: words still to expand
{
int size = queue.Count; // size: this ladder length only
for (int k = 0; k < size; k++) // k: words taken from this ring
{
string word = queue.Dequeue();
if (word == endWord)
return steps;
char[] chars = word.ToCharArray(); // one buffer per word, not per candidate
for (int i = 0; i < chars.Length; i++) // i: the position being changed
{
char original = chars[i];
// 'a' to 'z': try all 26 lowercase letters in this position.
for (char letter = 'a'; letter <= 'z'; letter++)
{
chars[i] = letter;
// A hit gives back the stored string, so nothing new is built.
if (lookup.TryGetValue(chars, out string? found))
{
words.Remove(found); // mark on push
queue.Enqueue(found);
}
}
chars[i] = original; // restore before moving to the next position
}
}
steps++; // + 1: the next ring adds one word
}
return 0; // 0: queue ran dry, no ladder exists
}
}
This version does not skip letter == original. The current word was already removed from words, so it can never match itself.
// Sketch, not full code. Search from both ends and always expand the
// smaller frontier. If the branching factor is b and the answer is at
// depth d, this visits about 2 * b^(d/2) nodes instead of b^d.
// 2 *: two searches. d/2: each only goes half the depth.
var front = new HashSet<string> { beginWord };
var back = new HashSet<string> { endWord };
// Invariant: front and back are the current frontiers, and they do not touch yet.
while (front.Count > 0 && back.Count > 0) // > 0: both sides can still grow
{
if (front.Count > back.Count)
(front, back) = (back, front); // tuple swap: always expand the cheaper side
// ... expand front one level. If a neighbour is in back, the halves meet.
}
On a real dictionary this is often several times faster. Mention it with the b^(d/2) argument. It is a strong finish to this question.
endWord not in the dictionary: return 0 at once. This check is required for correctness.beginWord == endWord: returns 1 on the first dequeue. Confirm that is the expected answer.beginWord may or may not be in the dictionary. HashSet<T>.Remove just returns false for a missing key, so no guard is needed.'a' to 'z'. Confirm the alphabet.0.Queue<T>. C# has no deque, and BFS does not need one. List<T>.RemoveAt(0) is O(n).queue.Count into a local at the top of the round. A for condition re-reads it on every pass.if (seen.Add(x)) queue.Enqueue(x); does it in one line.Pattern 8, Depth-First Search, is the other traversal. It cannot find shortest paths. But it does what BFS finds awkward. It lists every path, computes a value bottom-up from the leaves, and flood-fills a connected region.