> But in my example this is not hard to get right in C. The tree is constructed (on the stack would be fine), then used for a while without mutating it, then freed all at once.

It's still "hard to get right" in that at any time nothing is stopping you from violating any of the assumptions that make this "easy". It's never easy to write a solution that's "guaranteed to be safe" in C, but that's what you're trying to do by writing such a solution in Rust. To give but one example, nothing in C will stop your nodes from containing some resources which needs to be manually destructed and which get leaked when the stack frame is reclaimed.

Rust is going to require you to make those assumptions explicit, so that it can enforce them -- in this case, you need to explicitly restrict your solution to dealing with Copy types, which by construction don't implement Drop, and therefore have no destructors.

But at the end of the day, if all you want to do is swear to the compiler that you know what you're doing and you promise to not be stupid, wrap it in an unsafe and get C-style consequences if you got things wrong. You get C-Style easiness only by explicitly abandoning the attempt at guaranteeing safety for every type and scenario your solution could be used with.