Building Huffman Trees in C, Live and Unfiltered

Dr. Jonas Birch sits somewhere interesting in the systems programming tutorial ecosystem. His channel isn't chasing the algorithm-for-interviews crowd, and he's not producing the kind of polished, sponsor-laden content that dominates YouTube CS education. His ongoing series on coding your own operating system in C and assembly has built a following among people who think the right way to understand a computer is to argue with it directly, at the lowest level that doesn't involve soldering. His latest episode, coding a Huffman tree in C, lands squarely in that tradition: unscripted, genuinely exploratory, and not particularly interested in making things look easy.

That context matters for why this tutorial is worth your attention. Birch isn't teaching Huffman coding to people who need a leetcode refresher. He's building toward a compressor, probably for use in his OS project, which means the design decisions he makes here carry actual downstream weight. When he chooses a union to represent both leaves and nodes in a single tree type, he's not illustrating a textbook concept. He's solving a real structural problem: a sorted list of tree elements needs to hold both character leaves and internal nodes interchangeably, without the overhead of a vtable or the abstraction cost of a tagged void pointer scheme. That's a choice with consequences, and he makes it on camera, narrating the reasoning as he goes.

What Huffman actually does, and why C is a loaded choice for teaching it

The algorithm itself is about a century old, conceptually. As Virginia Tech's CS3 materials describe it, a Huffman code derives from a full binary tree built on character frequencies: the more often a character appears, the shorter its bit representation. Programiz summarizes the construction as building the tree first from frequency data, then deriving codes from the tree's structure. Birch opens with exactly that sequence: count characters, sort by frequency, pair the lowest-frequency elements, build upward. Four steps. Done. The algorithm isn't the hard part.

The hard part, in C, is the data structure design that makes the algorithm actually work. And this is where Birch's choice of language becomes a live argument, not just a stylistic preference.

The systems programming community is currently having a specific fight about C. The short version: Rust exists, memory safety is provably achievable, and the number of critical CVEs traced to C's manual memory management is not a philosophical concern but a documented body count. The Linux kernel's gradual, contested Rust adoption is one front of this fight. Mozilla's decision to rewrite core browser components in Rust is another. Against that backdrop, a tutorial that builds a tree data structure in C using malloc, pointer arithmetic, and unions is not a neutral pedagogical choice. It's a position.

I don't think Birch is making a political statement by choosing C. He's building an OS, and C is still the language in which most operating systems exist. The Huffman tree is a component of a larger project, and switching languages mid-project for a compressor module would be its own kind of chaos. But the choice does mean the tutorial carries the full weight of C's manual memory model, and the seg fault that arrives during testing makes that point more vividly than any slide deck could.

The union problem, and what it teaches

Birch's core data structure is a union tree that can be either a struct leaf (holding a character, a frequency counter, and an upstream connector) or a struct node (holding left and right downstream connectors, an upstream connector, and a frequency). The union lets a sorted list treat both types as the same pointer-sized thing, which is exactly what you need when you're building the tree bottom-up from a frequency-sorted list.

"We need to have a solid data type that can handle all of this," he says, "and that's where we are going to begin."

The frequency field is typed as int64 because, as Birch reasons aloud, the input might be a large file. The character field is int8. The upstream and downstream connectors are tree pointers. Straightforward on paper.

The problem arrives when he starts writing the node constructor and tries to access frequency fields on the union's members using arrow notation, treating the embedded structs as pointers when they're actually embedded values. The seg fault that follows is not a beginner's mistake exactly; it's the kind of thing that happens when you're designing a data structure by thinking through it in real time rather than speccing it on a whiteboard first. The union's memory layout makes pointer-to-member assumptions dangerous in ways that aren't immediately obvious.

"These unions are not always so straightforward," Birch says, after several minutes of debugging, just before the fix clicks into place.

The fix is a search-and-replace from arrow-notation to dot-notation through the affected struct members, acknowledging that the embedded structs in the union are values, not pointers. It works. The tree prints correctly: a node with frequency five, connected left to a leaf with frequency four (character 'A') and right to a leaf with frequency one (character 'B'), with upstream and downstream connections all intact.

What the debugging sequence actually demonstrates

The seg fault sequence is where this tutorial earns its runtime, and where Birch's approach diverges most sharply from the edited, mistake-free pedagogy that dominates the space.

Watching him work through it is instructive in a way that a clean solution wouldn't be. He uses return-statement bisection to isolate the crash site. He runs ltrace and acknowledges it didn't help. He considers multiple hypotheses, eliminates them one by one, and arrives at the correct diagnosis through the kind of incremental, unglamorous reasoning that actual debugging requires. None of this is scripted. At one point he says, "I don't see how this could seg fault, but it can. It most definitely can."

That's the sentence that should go on a poster in every CS department that teaches C. Manual memory management doesn't just fail at the obvious moments. It fails at the moments you were confident about.

Programming Logic's implementation guide for Huffman coding in C covers the frequency-analysis and tree-construction phases at a higher level, with cleaner code. It's a useful reference. But it doesn't show you what the union member access confusion looks like when it happens, or how you find it. Birch does.

This is the pedagogical bet he's making: that seeing the mistake and the recovery teaches something that seeing only the solution cannot. I think he's right about that, and I think it's a bet that scales better to the actual experience of writing systems code than the alternative. Nobody ships C without debugging it. The question is whether your first encounter with union memory layout confusion happens in a tutorial or in production.

The Rust question this tutorial sidesteps

Here's the thing Birch doesn't address, and that I think is worth naming directly: the problem he spent significant debugging time on, pointer arithmetic confusion in a union-based tagged type, is a category of bug that Rust's type system catches at compile time. The enum in Rust that would represent this union tree would give you pattern matching, exhaustiveness checking, and the guarantee that you cannot dereference a node as a leaf without the compiler noticing. The seg fault simply doesn't exist in that version of this code.

That's not an argument that Birch should be teaching this in Rust. His project context makes C the right tool. But it does locate this tutorial in a real argument the community is having: when we teach systems programming fundamentals in C, we're also teaching people to navigate a class of errors that newer systems languages have largely eliminated. The debugging practice is real. The lesson about union semantics is real. And so is the question of whether, for a learner starting fresh today with no existing OS project to maintain, C is still the first-principles language worth that cost.

Birch closes the episode noting that the hard structural work is done, and that sorting and text parsing come next. Whether the series eventually produces a working compressor for his OS project is an open question. But the union is connected, the tree prints, and the seg fault is gone.

For now, that's enough.