Follow one path to the end, then unwind and try the next. The call stack keeps the path for you. That is why DFS code is so much shorter than the problem sounds.
BFS answers “how far”. DFS answers “which paths” and “what is true of this whole subtree”. It is the workhorse of tree questions. Most tree questions are naturally recursive: the answer for a node combines the answers for its children. In C# there is one extra thing to watch. The call stack is small, about 1 MB, and overflowing it kills the process. This page shows when to switch to an explicit Stack<T>. The Python version of this page is here.
Queue<T>. DFS gets its stack for free.Almost every DFS question is one of these three. Name the shape before you write. It is the fastest way to get the code right.
void./// <summary>A binary tree node.</summary>
/// <example>new TreeNode(3, new TreeNode(9), new TreeNode(20)) is a root with two leaves.</example>
public class TreeNode(int val = 0, TreeNode? left = null, TreeNode? right = null)
{
public int Val { get; set; } = val; // 0 default: payload when none is given
public TreeNode? Left { get; set; } = left; // null: no left child
public TreeNode? Right { get; set; } = right; // null: no right child
}
/// <summary>An undirected graph node with an adjacency list.</summary>
/// <example>var a = new GraphNode(1); a.Neighbors.Add(new GraphNode(2));</example>
public class GraphNode(int val = 0)
{
public int Val { get; } = val; // 0 default: payload when none is given
// [] runs once per new node, so every node gets its own fresh list.
// C# has no shared-mutable-default trap like Python's def f(x=[]).
public List<GraphNode> Neighbors { get; set; } = [];
}
Both are plain classes, not records. A class compares by reference, so two different nodes are never “equal”. Clone Graph depends on that.
public static class BottomUpTemplate
{
/// <summary>Combine the children's answers into this node's answer.</summary>
/// <param name="node">Subtree root, or null for an empty subtree.</param>
/// <returns>The answer for the whole subtree.</returns>
/// <example>Summarise(tree 3 / (9, 20 / (15, 7))) returns 3 with the depth Combine.</example>
public static int Summarise(TreeNode? node)
{
// 0: the answer for an empty subtree. Max Depth: an empty tree has depth 0.
// This base case defines the whole recursion.
if (node is null) return 0;
// Trust the calls: each returns the full answer for its subtree.
int left = Summarise(node.Left);
int right = Summarise(node.Right);
return Combine(node.Val, left, right);
}
// Combine(val, left, right): placeholder that builds this node's answer from its
// children's. Max Depth example: 1 + the deeper side. The 1 counts this node.
private static int Combine(int val, int left, int right) => 1 + Math.Max(left, right);
}
public static class TopDownTemplate
{
/// <summary>Record every root-to-leaf path that qualifies.</summary>
/// <param name="root">Tree root, or null.</param>
/// <param name="qualifies">Placeholder test: does this full path count?
/// Path Sum II example: trail => trail.Sum() == 22.</param>
/// <returns>Copies of every qualifying path, in traversal order.</returns>
/// <example>Collect(tree 1 / (2, 3), t => true) returns [[1, 2], [1, 3]].</example>
public static List<List<int>> Collect(TreeNode? root, Func<List<int>, bool> qualifies)
{
var results = new List<List<int>>();
var trail = new List<int>(); // values from the root down to the current node
// Invariant: on entry and on exit, trail is the path to node's parent.
void Walk(TreeNode? node)
{
if (node is null) return; // past a leaf: nothing to record
trail.Add(node.Val); // choose
// Both children null means a leaf, so trail is a full root-to-leaf path.
if (node.Left is null && node.Right is null)
{
if (qualifies(trail)) results.Add([.. trail]); // COPY: trail keeps changing
}
else
{
Walk(node.Left);
Walk(node.Right);
}
// Count - 1: index of the last value. Remove it to un-choose: the backtrack.
trail.RemoveAt(trail.Count - 1);
}
Walk(root);
return results;
}
}
Choose, recurse, un-choose. Every top-down DFS with a shared mutable trail has this shape. It is the same shape as backtracking. Walk is a local function, so it can read trail and results without passing them in. [.. trail] is a collection expression with a spread, which makes a new list.
Reading the figure. Each column is the trail list after one step, with the root at the bottom. Amber is a value just pushed. Green is a push that reached a leaf, where a copy is recorded. Blue values are lower on the path. Red labels mark the un-choose step. Notice that the trail grows and shrinks like the call stack in Figure 8.1, and ends empty.
public static class FloodTemplate
{
// Down, up, right, left as (row step, col step). No diagonals.
private static readonly (int Dr, int Dc)[] Steps = [(1, 0), (-1, 0), (0, 1), (0, -1)];
/// <summary>Mark the whole connected region containing (r, c). No overflow risk.</summary>
/// <param name="grid">Rows of '1' (land) and '0' (water). Mutated: land becomes '0'.</param>
/// <param name="r">Start row. Must be a land cell.</param>
/// <param name="c">Start column.</param>
/// <example>Flood([['1','1'],['0','1']], 0, 0) leaves every cell '0'.</example>
public static void Flood(char[][] grid, int r, int c)
{
int rows = grid.Length, cols = grid[0].Length; // grid[0]: every row has this width
var stack = new Stack<(int Row, int Col)>();
stack.Push((r, c));
grid[r][c] = '0'; // '0': mark on push so it is never pushed twice
// Invariant: every cell on the stack is land already marked '0'.
while (stack.Count > 0) // > 0: cells still waiting to spread
{
var (row, col) = stack.Pop(); // Pop takes the newest: LIFO, so depth-first
// (dr, dc): one of the four steps around the current cell.
foreach (var (dr, dc) in Steps)
{
int nr = row + dr, nc = col + dc;
// 0 <= ... < rows/cols: stay on the grid. '1': unvisited land only.
if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr][nc] == '1')
{
grid[nr][nc] = '0'; // '0': sink it so no one pushes it again
stack.Push((nr, nc));
}
}
}
}
}
Stack<T> lives on the heap, so it can hold millions of cells. The call stack cannot. The tuple (int Row, int Col) is a value type, so each push stores two ints and allocates nothing.
Reading the figure. Violet cells are land not reached yet. Amber cells are on the stack, and they already read '0' because marking happens on push. Red cells were popped and are done. Grey cells are water. Notice that (0,0) is never pushed again when (0,1) looks back at it.
results.Add(trail) stores a reference to a list that keeps changing. Every result ends up the same object, usually empty. Use [.. trail] or new List<int>(trail).RemoveAt, the trail grows forever. Every path after the first is wrong.StackOverflowException, and .NET cannot catch it. The whole process dies. Use the iterative version, or say why the depth is bounded.0 where it should be int.MinValue, or true where it should be false.Return the number of nodes along the longest path from the root down to the furthest leaf.
0, so a leaf gets 1 + Math.Max(0, 0) = 1. No special leaf handling is needed.public static class MaxDepthOfBinaryTree
{
/// <summary>Number of nodes on the longest root-to-leaf path.</summary>
/// <param name="root">Root node, or null.</param>
/// <returns>0 for an empty tree, 1 for a single node, and so on.</returns>
/// <example>MaxDepth(tree [3, 9, 20, null, null, 15, 7]) returns 3.</example>
public static int MaxDepth(TreeNode? root)
{
if (root is null) return 0; // 0: an empty tree has no nodes on any path
// 1 +: count this node, then add the deeper of the two subtrees.
return 1 + Math.Max(MaxDepth(root.Left), MaxDepth(root.Right));
}
}
Reading the figure. This uses the tree 3, 9, 20, 15, 7 from the BFS page. Blue nodes have finished and returned the purple number. Purple arrows show a child’s answer flowing up to its parent. The green root holds the final answer. The deeper side, through 20, decides the result.
public static class MaxDepthWithStack
{
/// <summary>Same answer with an explicit stack of (node, depth) pairs.</summary>
/// <param name="root">Root node, or null.</param>
/// <returns>0 for an empty tree, else the node count of the longest path.</returns>
/// <example>MaxDepth(a left-leaning chain of 100,000 nodes) returns 100000.</example>
public static int MaxDepth(TreeNode? root)
{
if (root is null) return 0; // 0: an empty tree has depth 0
int best = 0; // 0: no depth seen yet
var stack = new Stack<(TreeNode Node, int Depth)>();
stack.Push((root, 1)); // 1: the root alone is a path of one node
// Invariant: best is the deepest depth among nodes popped so far, and
// every pair on the stack carries its node's correct depth.
while (stack.Count > 0) // > 0: nodes still to visit
{
var (node, depth) = stack.Pop();
best = Math.Max(best, depth);
// depth + 1: a child sits one level below its parent.
if (node.Left is not null) stack.Push((node.Left, depth + 1));
if (node.Right is not null) stack.Push((node.Right, depth + 1));
}
return best;
}
}
Space is O(log n) on a balanced tree and O(n) on a degenerate one. Say that, not just “O(h)”. It shows you know what h can be.
Math.Min. But a node with one null child is not a leaf, so it needs a special case. Classic trap.-1 upward the moment a subtree is unbalanced.best with left + right. A local function can write to a local variable of the outer method.1 + Count(left) + Count(right).0.1.Return every root-to-leaf path whose node values sum to targetSum. Each path is the list of values along it.
trail list. Add on the way down, remove on the way back up. That is O(h) space, not a fresh list per branch.public static class PathSumII
{
/// <summary>All root-to-leaf paths whose values sum to targetSum.</summary>
/// <param name="root">Root node, or null.</param>
/// <param name="targetSum">The required total. Values may be negative.</param>
/// <returns>A list of paths, each a list of values from root to leaf.</returns>
/// <example>Tree 5 / (4, 8) ... with target 22 returns [[5, 4, 11, 2], [5, 8, 4, 5]].</example>
public static List<List<int>> PathSum(TreeNode? root, int targetSum)
{
var paths = new List<List<int>>();
var trail = new List<int>(); // values from the root down to the current node
// remaining: how much the rest of the path still has to add up to.
// Invariant: on entry and on exit, trail is the path to node's parent.
void Walk(TreeNode? node, int remaining)
{
if (node is null) return; // past a leaf: no path here
trail.Add(node.Val); // choose
remaining -= node.Val; // this node pays part of the target
// Both children null means a leaf. Only full paths may count.
if (node.Left is null && node.Right is null)
{
// == 0: the path used up the target exactly.
if (remaining == 0) paths.Add([.. trail]); // copy: trail keeps changing
}
else
{
Walk(node.Left, remaining);
Walk(node.Right, remaining);
}
// Count - 1: index of the last value. Un-choose, on every exit path.
trail.RemoveAt(trail.Count - 1);
}
Walk(root, targetSum); // the whole target is still owed at the root
return paths;
}
}
Left is null && Right is nullremaining == 0, you report paths that stop halfway down. That is wrong. Suppose you recurse into a null child and test there instead. Then a one-child node whose partial sum matches gets reported twice, once per null. Test for a real leaf, explicitly.[.. trail] and not trailList<int> is a reference type. trail is one list that changes all through the walk. Adding it stores a reference to that one list. By the time the method returns, every stored reference points at the same, now empty, list. This is the most common bug in every backtracking problem, not just this one.
Take the tree with root 5, children 4 and 8, and target 22. The recursion drives down 5 → 4 → 11 → 7. That sums to 27, no match. It pops back to 11 and tries 2, which gives 22 and a recorded path. It unwinds to the root, removing each value. Then it explores the 8 branch.
Reading the figure. Each leaf shows the sum of its root-to-leaf path. Green leaves and edges sum to 22 and are recorded. Red leaves miss the target. The boxes on the right are trail at the first hit. After that leaf, the walk pops values on the way back up, then tries the 8 branch.
Visiting is O(n). But copying a qualifying path costs O(h) each time. A pathological tree can have O(n) of them.
[], even if targetSum is 0. A path needs at least one node.remaining < 0. Ask whether all values are positive before adding that.int is 32-bit. With huge values, remaining can wrap. Ask about the range, and use long if needed.A grid holds '1' for land and '0' for water. An island is a group of land cells joined up, down, left or right. Count the islands. In C# the grid is a char[][], a jagged array, as on LeetCode.
'0' into the grid is the visited marker. So extra space is just the stack. If you may not change the input, use a bool[,] visited and say so.public static class NumberOfIslands
{
// 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>Count connected regions of '1' in a grid, using 4-directional adjacency.</summary>
/// <param name="grid">Rows of '1' (land) and '0' (water). Mutated: land is sunk
/// to '0' as it is visited.</param>
/// <returns>The number of islands.</returns>
/// <example>NumIslands([['1','1','0'], ['0','1','0'], ['0','0','1']]) returns 2.</example>
public static int NumIslands(char[][] grid)
{
// Length == 0: no rows, or a first row with no columns. Either way no cells.
if (grid.Length == 0 || grid[0].Length == 0) return 0; // 0: no cells, no islands
int rows = grid.Length, cols = grid[0].Length; // grid[0]: every row has this width
int islands = 0; // 0: none found yet
// Flood the region containing (startR, startC), iteratively.
// An explicit Stack<T> avoids the 1 MB call stack, which a large
// all-land grid would otherwise overflow.
void Sink(int startR, int startC)
{
var stack = new Stack<(int R, int C)>();
stack.Push((startR, startC));
grid[startR][startC] = '0'; // '0': sink on push so it is never pushed twice
// Invariant: every cell on the stack is land already sunk to '0'.
while (stack.Count > 0) // > 0: cells still waiting to spread
{
var (r, c) = stack.Pop(); // Pop takes the newest: LIFO, so depth-first
// (dr, dc): one of the four steps around (r, c).
foreach (var (dr, dc) in Directions)
{
int nr = r + dr, nc = c + dc;
// 0 <= ... < rows/cols: stay on the grid. '1': unsunk land only.
if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr][nc] == '1')
{
grid[nr][nc] = '0'; // mark on push
stack.Push((nr, nc));
}
}
}
}
// Scan every cell. Invariant: every island touching a scanned cell is
// counted and fully sunk, so no '1' left behind belongs to it.
// r: current row, 0..rows-1. c: current column, 0..cols-1.
for (int r = 0; r < rows; r++)
{
for (int c = 0; c < cols; c++)
{
if (grid[r][c] == '1') // '1': land no flood has reached
{
islands++; // + 1: a region we have not seen before
Sink(r, c);
}
}
}
return islands;
}
}
Take [['1','1','0'],['0','1','0'],['0','0','1']]. The scan hits (0,0) and counts island 1. It sinks (0,0), (0,1) and (1,1). The scan moves on over cells that are now water until (2,2). It counts island 2 and sinks it. The answer is 2.
Reading the figure. Violet cells are land not visited yet. Amber is the land cell the scan just found, which adds one to the count. Red cells are sunk to '0'. Grey cells are water. Between frame 2 and frame 3 the scan passes over the red cells without counting them.
The outer scan looks at every cell once. Each cell is pushed at most once. So the total is linear in the number of cells, despite the nested loops.
public static class IslandsRecursive
{
// Down, up, right, left as (row step, col step). No diagonals.
private static readonly (int Dr, int Dc)[] Steps = [(1, 0), (-1, 0), (0, 1), (0, -1)];
/// <summary>Elegant, but the call depth equals the region size.</summary>
/// <param name="grid">The grid. Land in the region becomes '0'.</param>
/// <param name="r">Row to try. May be off the grid.</param>
/// <param name="c">Column to try. May be off the grid.</param>
/// <example>Sink([['1','1']], 0, 0) turns the grid into [['0','0']].</example>
public static void Sink(char[][] grid, int r, int c)
{
// Off the grid (below 0 or past the last index), or not unvisited land: stop.
if (r < 0 || r >= grid.Length || c < 0 || c >= grid[r].Length || grid[r][c] != '1')
return;
grid[r][c] = '0'; // '0': sink before recursing, or we loop forever
// (dr, dc): spread to each of the 4 neighbours.
foreach (var (dr, dc) in Steps) Sink(grid, r + dr, c + dc);
}
}
RecursionError. StackOverflowException cannot be caught, so the process just ends. Write the recursive version if it is clearer. Then say “in production I would make this iterative because the depth is unbounded.” That sentence is worth real points.0.1. It is the worst case for stack depth.var visited = new bool[rows, cols], at O(rows × cols) extra memory. A rectangular bool[,] is one block of memory, so it is cheap to make.You get a reference to a node in a connected, undirected graph. Return a deep copy of the whole graph. Each node holds a value and a list of neighbours.
This map does three jobs at once. It is the visited set. It is where partly built clones live. And it lets a second edge into the same node find the same clone, not a duplicate.
public static class CloneGraph
{
/// <summary>Deep-copy a connected undirected graph reachable from node.</summary>
/// <param name="node">Any node of the graph, or null for an empty graph.</param>
/// <returns>The clone of node, with the whole graph copied.</returns>
/// <example>Clone(node 1 of cycle 1-2-3-4-1) returns a new 1 linked to new 2 and 4.</example>
public static GraphNode? Clone(GraphNode? node)
{
if (node is null) return null; // empty graph: nothing to copy
// original -> its clone. Doubles as the visited set, so cycles stop.
// ReferenceEqualityComparer: match by identity even if Equals is ever overridden.
var clones = new Dictionary<GraphNode, GraphNode>(ReferenceEqualityComparer.Instance);
GraphNode Copy(GraphNode original)
{
// TryGetValue: one lookup that also hands back the clone if it exists.
if (clones.TryGetValue(original, out var existing))
return existing; // already built, or being built right now
var duplicate = new GraphNode(original.Val);
clones[original] = duplicate; // REGISTER FIRST, then recurse
// neighbour: each original neighbour in order. Clone it (or find it), then link.
foreach (var neighbour in original.Neighbors)
duplicate.Neighbors.Add(Copy(neighbour));
return duplicate;
}
return Copy(node);
}
}
public static class CloneGraphWithQueue
{
/// <summary>Same result with an explicit queue, so there is no stack depth limit.</summary>
/// <param name="node">Any node of the graph, or null for an empty graph.</param>
/// <returns>The clone of node, with the whole graph copied.</returns>
/// <example>Clone(a self-looped node) returns a clone whose neighbour is itself.</example>
public static GraphNode? Clone(GraphNode? node)
{
if (node is null) return null; // empty graph: nothing to copy
// original -> its clone. Build the start node's clone up front.
var clones = new Dictionary<GraphNode, GraphNode>(ReferenceEqualityComparer.Instance)
{
[node] = new GraphNode(node.Val),
};
var queue = new Queue<GraphNode>(); // FIFO is enough: we only take from the front
queue.Enqueue(node);
// Invariant: every node in the queue already has a clone in clones.
// Its clone's neighbour list is filled in when the node is dequeued.
while (queue.Count > 0) // > 0: nodes whose links are not copied yet
{
var original = queue.Dequeue();
// neighbour: each original neighbour, in order.
foreach (var neighbour in original.Neighbors)
{
// First sighting: make its clone now and queue it once.
if (!clones.TryGetValue(neighbour, out var twin))
{
twin = new GraphNode(neighbour.Val);
clones[neighbour] = twin;
queue.Enqueue(neighbour);
}
// Link the clones in the same order as the originals.
clones[original].Neighbors.Add(twin);
}
}
return clones[node]; // the clone of the start node
}
}
C# has no built-in deque. This version does not need one. Queue<T> is a ring buffer with O(1) Enqueue and Dequeue, and that is all BFS uses.
Take the four-node cycle 1 – 2 – 3 – 4 – 1. Copy(1) registers clone 1, then recurses to 2. That registers clone 2, then goes to 3, then to 4. Node 4’s neighbours are 3 and 1. Both are already in the map, so both return at once. The cycle closes with no endless recursion. The recursion then unwinds, filling in each neighbour list.
Reading the figure. Blue nodes are on the call stack, still waiting for their neighbour lists. Amber is the current call, Copy(4). The middle column is clones, filled in the order shown. On the right, 4′ is the clone of node 4. Its green links are done. The dashed links are made as the other calls return.
Each node is created once. Each edge is walked once from each side.
node is null: return null.Copy finds the node already registered and links the clone to itself. That works because of the register-first order.Dictionary uses Equals and GetHashCode. A class uses identity by default, so the code works as is. But a record, or a class that overrides Equals by value, could make two different nodes look equal. Passing ReferenceEqualityComparer.Instance rules that out.void.[.. trail].Stack<T> form of any DFS whose depth is not clearly bounded.Pattern 9, Top K Elements, changes the tool. It uses a heap, PriorityQueue<TElement, TPriority>, instead of a traversal. The trick is that you almost never need the data sorted, only its extremes.