Trees are the other structure C# does not ship for you. There is no BinaryTreeNode<T> in the BCL, so every program here declares one:
class TreeNode(int value, TreeNode? left = null, TreeNode? right = null)
{
public int Value = value;
public TreeNode? Left = left, Right = right;
}This part is traversal only — getting to every node, in a useful order. Part 13 is what you compute once you are there.
Every program below is complete, was run on .NET 10, and its output is pasted from the run.
Pattern 56 — The three recursive orders
Pre-order, in-order and post-order are the same function three times. The only difference is which line the visit sits on.
The three functions are identical except for which line the visit sits on. That single line of difference is the entire distinction, and it decides whether a node is handled before or after the answers from its children exist.
// 1
// / \
// 2 3
// / \ /
// 4 5 6
TreeNode tree = new(1,
new TreeNode(2, new TreeNode(4), new TreeNode(5)),
new TreeNode(3, new TreeNode(6)));
// The three orders differ by ONE line: where the visit sits relative to the
// two recursive calls.
static void PreOrder(TreeNode? n, List<int> outp)
{
if (n is null) return;
outp.Add(n.Value); // visit, then children
PreOrder(n.Left, outp);
PreOrder(n.Right, outp);
}
static void InOrder(TreeNode? n, List<int> outp)
{
if (n is null) return;
InOrder(n.Left, outp);
outp.Add(n.Value); // left, visit, right
InOrder(n.Right, outp);
}
static void PostOrder(TreeNode? n, List<int> outp)
{
if (n is null) return;
PostOrder(n.Left, outp);
PostOrder(n.Right, outp);
outp.Add(n.Value); // children, then visit
}
foreach ((string name, Action<TreeNode?, List<int>> walk) in new (string, Action<TreeNode?, List<int>>)[]
{ ("pre-order ", PreOrder), ("in-order ", InOrder), ("post-order", PostOrder) })
{
List<int> got = [];
walk(tree, got);
Console.WriteLine($"{name} {string.Join(" ", got)}");
}
Console.WriteLine();
Console.WriteLine("pre-order visits a node BEFORE its subtrees -> copying a tree, serialising");
Console.WriteLine("in-order visits left, node, right -> a BST comes out sorted");
Console.WriteLine("post-order visits a node AFTER its subtrees -> freeing, or any answer that");
Console.WriteLine(" depends on both children");
class TreeNode(int value, TreeNode? left = null, TreeNode? right = null)
{
public int Value = value;
public TreeNode? Left = left, Right = right;
}It prints:
pre-order 1 2 4 5 3 6
in-order 4 2 5 1 6 3
post-order 4 5 2 6 3 1
pre-order visits a node BEFORE its subtrees -> copying a tree, serialising
in-order visits left, node, right -> a BST comes out sorted
post-order visits a node AFTER its subtrees -> freeing, or any answer that
depends on both childrenNaming them by position is how they are usually taught and it is not what makes them useful. The useful distinction is whether a node is handled before or after its children’s answers exist:
- Pre-order processes a node with nothing known about its subtrees. Good for copying a tree, serialising it, or anything where the node’s own data is enough.
- In-order on a binary search tree produces sorted output. That is not a coincidence — it is the definition of a BST expressed as a walk.
- Post-order processes a node once both children are done. Any answer that combines results from below is post-order, whether or not you call it that. All of part 13 is post-order.
Cost: O(n) time, O(h) space for the call stack, where h is the height.
Reach for it when — always. This is the vocabulary the rest of tree work is written in.
Pattern 57 — In-order without recursion
Part 7 established that C# terminates the process on a stack overflow, uncatchably, and that a degenerate tree is deep. So the iterative version matters more here than in some other languages.
The reason people cannot reconstruct it under pressure is that they try to remember the code. The code follows from naming what the stack holds.
Writing the stack by hand is only hard until you can name what is on it. Once “left done, not yet visited” is the invariant, the loop writes itself — and it cannot overflow the way the recursive version can on a degenerate tree.
// 4
// / \
// 2 6
// / \ /
// 1 3 5
TreeNode tree = new(4,
new TreeNode(2, new TreeNode(1), new TreeNode(3)),
new TreeNode(6, new TreeNode(5)));
// Recursion keeps its place implicitly, on the call stack. Doing it by hand
// means the stack holds the nodes whose LEFT side is done but which have not
// themselves been visited yet.
static List<int> InOrderIterative(TreeNode? root, bool trace)
{
List<int> outp = [];
Stack<TreeNode> st = [];
TreeNode? cur = root;
while (cur is not null || st.Count > 0)
{
while (cur is not null) // go as far left as possible
{
st.Push(cur);
if (trace) Console.WriteLine($" push {cur.Value} stack=[{string.Join(",", st.Select(x => x.Value).Reverse())}]");
cur = cur.Left;
}
cur = st.Pop(); // nothing further left: visit
outp.Add(cur.Value);
if (trace) Console.WriteLine($" pop {cur.Value} visit -> [{string.Join(" ", outp)}]");
cur = cur.Right; // then handle the right subtree
}
return outp;
}
var got = InOrderIterative(tree, true);
Console.WriteLine($"\nin-order: {string.Join(" ", got)}");
Console.WriteLine($"sorted: {got.SequenceEqual(got.Order())} <- it is a BST, so in-order is sorted");
class TreeNode(int value, TreeNode? left = null, TreeNode? right = null)
{
public int Value = value;
public TreeNode? Left = left, Right = right;
}It prints:
push 4 stack=[4]
push 2 stack=[4,2]
push 1 stack=[4,2,1]
pop 1 visit -> [1]
pop 2 visit -> [1 2]
push 3 stack=[4,3]
pop 3 visit -> [1 2 3]
pop 4 visit -> [1 2 3 4]
push 6 stack=[6]
push 5 stack=[6,5]
pop 5 visit -> [1 2 3 4 5]
pop 6 visit -> [1 2 3 4 5 6]
in-order: 1 2 3 4 5 6
sorted: True <- it is a BST, so in-order is sortedThe stack holds nodes whose left subtree is finished but which have not themselves been visited. That is exactly what the call stack was storing implicitly. Once that sentence is in your head, the loop is forced:
- Go left as far as possible, pushing everything on the way.
- Nothing further left? Pop it and visit it — its left side is done by construction.
- Then move to its right child, and go back to step 1.
The outer condition is cur is not null || st.Count > 0, and both halves are needed. The stack can be empty while there is still a right subtree to descend into, which is the case at the very start and again at node 4 in that trace.
Cost: O(n) time, O(h) space — the same space, but on the heap where it cannot kill the process.
Reach for it when the tree might be deep, or when the problem wants the traversal paused and resumed — a BST iterator is this loop with the middle taken out.
Pattern 58 — Level order
Depth-first has been every pattern so far. Level order is breadth-first, and it is the same queue from part 7 with one addition.
The problem: a queue is one flat sequence and knows nothing about levels. Nodes from level 2 are enqueued while level 1 is still being drained, so they are all mixed together.
A queue does not know about levels — it is one flat sequence. The boundary is recovered by snapshotting how many nodes were waiting at the moment the level began.
// 1
// / \
// 2 3
// / \ \
// 4 5 6
// /
// 7
TreeNode tree = new(1,
new TreeNode(2, new TreeNode(4), new TreeNode(5, new TreeNode(7))),
new TreeNode(3, null, new TreeNode(6)));
// The queue naturally mixes levels together. Capturing Count BEFORE the inner
// loop is what puts the boundaries back.
static List<List<int>> LevelOrder(TreeNode? root)
{
List<List<int>> levels = [];
if (root is null) return levels;
Queue<TreeNode> q = [];
q.Enqueue(root);
while (q.Count > 0)
{
int width = q.Count; // exactly this many nodes are on this level
List<int> level = [];
for (int i = 0; i < width; i++)
{
TreeNode n = q.Dequeue();
level.Add(n.Value);
if (n.Left is not null) q.Enqueue(n.Left);
if (n.Right is not null) q.Enqueue(n.Right);
}
levels.Add(level);
Console.WriteLine($"level {levels.Count - 1}: width was {width}, values [{string.Join(", ", level)}], queue now holds {q.Count}");
}
return levels;
}
var levels = LevelOrder(tree);
Console.WriteLine($"\nlevels: [{string.Join("], [", levels.Select(l => string.Join(", ", l)))}]");
Console.WriteLine($"depth: {levels.Count}");
class TreeNode(int value, TreeNode? left = null, TreeNode? right = null)
{
public int Value = value;
public TreeNode? Left = left, Right = right;
}It prints:
level 0: width was 1, values [1], queue now holds 2
level 1: width was 2, values [2, 3], queue now holds 3
level 2: width was 3, values [4, 5, 6], queue now holds 1
level 3: width was 1, values [7], queue now holds 0
levels: [1], [2, 3], [4, 5, 6], [7]
depth: 4The whole trick is int width = q.Count; before the inner loop. That snapshot is how many nodes belong to this level, and draining exactly that many gets the boundary right.
Write for (int i = 0; i < q.Count; i++) instead and the condition is re-evaluated each iteration against a queue that is growing as children are added. The level never ends, and you get a single flat list — the trace above shows the count changing from 2 to 3 mid-level, which is exactly what would go wrong.
Cost: O(n) time, O(w) space where w is the widest level.
Reach for it when the problem mentions levels, depth, or nearest. Minimum depth in particular should be BFS, not DFS — BFS can stop at the first leaf it meets, while DFS has to explore everything.
Pattern 59 — Zigzag, side views, and the rest
Once level order exists, a surprising number of tree problems are one line on top of it.
TreeNode tree = new(1,
new TreeNode(2, new TreeNode(4), new TreeNode(5, new TreeNode(7))),
new TreeNode(3, null, new TreeNode(6)));
static List<List<int>> Levels(TreeNode? root)
{
List<List<int>> levels = [];
if (root is null) return levels;
Queue<TreeNode> q = [];
q.Enqueue(root);
while (q.Count > 0)
{
int width = q.Count;
List<int> level = [];
for (int i = 0; i < width; i++)
{
TreeNode n = q.Dequeue();
level.Add(n.Value);
if (n.Left is not null) q.Enqueue(n.Left);
if (n.Right is not null) q.Enqueue(n.Right);
}
levels.Add(level);
}
return levels;
}
var levels = Levels(tree);
// Zigzag: do NOT alternate the traversal. Reverse alternate rows afterwards.
var zigzag = levels.Select((l, i) => i % 2 == 1 ? Enumerable.Reverse(l).ToList() : l).ToList();
// Right side view: the last value of each level.
var rightView = levels.Select(l => l[^1]).ToList();
// Left side view is the first of each level, for free.
var leftView = levels.Select(l => l[0]).ToList();
Console.WriteLine($"levels : [{string.Join("], [", levels.Select(l => string.Join(", ", l)))}]");
Console.WriteLine($"zigzag : [{string.Join("], [", zigzag.Select(l => string.Join(", ", l)))}]");
Console.WriteLine($"right view : {string.Join(", ", rightView)}");
Console.WriteLine($"left view : {string.Join(", ", leftView)}");
Console.WriteLine($"max depth : {levels.Count}");
Console.WriteLine($"widest : {levels.Max(l => l.Count)} nodes, at level {levels.FindIndex(l => l.Count == levels.Max(x => x.Count))}");
Console.WriteLine();
Console.WriteLine("Every one of these is the level list plus one line. Trying to build");
Console.WriteLine("zigzag by alternating the traversal itself is where people tie themselves");
Console.WriteLine("in knots — the queue order stays the same, only the output is reversed.");
class TreeNode(int value, TreeNode? left = null, TreeNode? right = null)
{
public int Value = value;
public TreeNode? Left = left, Right = right;
}It prints:
levels : [1], [2, 3], [4, 5, 6], [7]
zigzag : [1], [3, 2], [4, 5, 6], [7]
right view : 1, 3, 6, 7
left view : 1, 2, 4, 7
max depth : 4
widest : 3 nodes, at level 2
Every one of these is the level list plus one line. Trying to build
zigzag by alternating the traversal itself is where people tie themselves
in knots — the queue order stays the same, only the output is reversed.Zigzag is where people tie themselves in knots, because the instinct is to alternate the traversal — enqueue right-before-left on odd levels, or swap the queue for a stack. That works and it is fiddly and it is easy to get wrong.
The queue order does not need to change. Build the levels normally, then reverse alternate rows. Same answer, one line, nothing to debug.
The side views are the last and first element of each level. Maximum depth is the count. The widest level is a Max. None of these need their own algorithm.
Reach for it when any question is phrased per-level. Build the levels, then answer the question about the list.
Pattern 60 — Rebuilding a tree from two traversals
Given pre-order and in-order, reconstruct the tree.
One traversal is never enough — many different trees share a pre-order. Two, with in-order as one of them, pin it down exactly.
Find the root’s position in the in-order array with a dictionary, not a scan. A scan makes each level O(n) and the whole reconstruction O(n²) on a degenerate tree — which is exactly the input a test will use.
int[] preorder = [1, 2, 4, 5, 3, 6];
int[] inorder = [4, 2, 5, 1, 6, 3];
// pre-order gives you the ROOT first. in-order tells you how much of the rest
// belongs on each side of it. A dictionary makes "where is the root in inorder"
// O(1) instead of a scan, which is the difference between O(n) and O(n^2).
Dictionary<int, int> where = inorder.Select((v, i) => (v, i)).ToDictionary(t => t.v, t => t.i);
int cursor = 0;
TreeNode? Build(int lo, int hi, int depth)
{
if (lo > hi) return null;
int value = preorder[cursor++];
int mid = where[value];
Console.WriteLine($"{new string(' ', depth * 2)}root {value}: inorder[{lo}..{hi}], splits at {mid} " +
$"-> left [{lo}..{mid - 1}], right [{mid + 1}..{hi}]");
var node = new TreeNode(value);
node.Left = Build(lo, mid - 1, depth + 1); // must come first: it consumes
node.Right = Build(mid + 1, hi, depth + 1); // the pre-order cursor in order
return node;
}
TreeNode? root = Build(0, inorder.Length - 1, 0);
static void Pre(TreeNode? n, List<int> o) { if (n is null) return; o.Add(n.Value); Pre(n.Left, o); Pre(n.Right, o); }
static void In(TreeNode? n, List<int> o) { if (n is null) return; In(n.Left, o); o.Add(n.Value); In(n.Right, o); }
List<int> p = [], i = [];
Pre(root, p); In(root, i);
Console.WriteLine($"\nrebuilt pre-order: {string.Join(" ", p)} matches: {p.SequenceEqual(preorder)}");
Console.WriteLine($"rebuilt in-order : {string.Join(" ", i)} matches: {i.SequenceEqual(inorder)}");
class TreeNode(int value, TreeNode? left = null, TreeNode? right = null)
{
public int Value = value;
public TreeNode? Left = left, Right = right;
}It prints:
root 1: inorder[0..5], splits at 3 -> left [0..2], right [4..5]
root 2: inorder[0..2], splits at 1 -> left [0..0], right [2..2]
root 4: inorder[0..0], splits at 0 -> left [0..-1], right [1..0]
root 5: inorder[2..2], splits at 2 -> left [2..1], right [3..2]
root 3: inorder[4..5], splits at 5 -> left [4..4], right [6..5]
root 6: inorder[4..4], splits at 4 -> left [4..3], right [5..4]
rebuilt pre-order: 1 2 4 5 3 6 matches: True
rebuilt in-order : 4 2 5 1 6 3 matches: TrueTwo things carry it.
Pre-order’s first unconsumed value is always the next root. A single shared cursor walks it forward, which is why Build(left) must be called before Build(right) — the left subtree consumes its share of the pre-order first. Swap those two lines and the tree comes out mirrored, with no error.
In-order says where to split. Everything left of the root’s position belongs to the left subtree, everything right to the right. The where dictionary makes that lookup O(1); scanning the in-order array instead makes the whole reconstruction O(n²) on a degenerate tree, which is precisely the input a test case will choose.
Note the base case lo > hi handles the empty ranges in the trace — [0..-1] and [2..1] are how a missing child announces itself.
Post-order plus in-order works the same way, consuming post-order backwards and building right before left. Pre-order plus post-order does not determine a tree uniquely.
Cost: O(n) time and space.
Reach for it when you are handed two traversals, or serialising and deserialising a tree.
What to remember
-
The three orders differ by one line. What matters is whether a node is handled before or after its children’s answers exist.
-
In-order on a BST is sorted. That is the definition, walked.
-
The iterative stack holds “left done, not yet visited”. Name the invariant and the code follows; memorising the code does not survive pressure.
-
Snapshot
q.Countinto a local before draining a level. Re-reading it in the loop condition means the level never ends. -
Do not alternate the traversal for zigzag. Build the levels, reverse alternate rows.
-
Build the left subtree before the right. They share one pre-order cursor, and the order of those two calls is the whole difference between a tree and its mirror.
-
Index the in-order array with a dictionary. Scanning turns O(n) into O(n²) on exactly the input a test will pick.
Part 13 is what you do once you can reach every node: path sums, diameter, ancestors, and the distinction between what a recursion returns and what it carries down.