The solution linked to in "Go has a suitable answer" isn't relevant, because it doesn't support virtual methods. You can do the same thing described there in Rust by having a base struct, embedding the base struct in any child structs (composition over inheritance), and implementing Deref/DerefMut on the child if you like.

Go has the exact same set of features Rust has here, no more: struct composition or interfaces/traits.

Regarding graphs: The best solution is option 3, using a crate on crates.io (petgraph is the most popular, but rust-forest is fine too). The preferred solution to having multiple types of nodes in the same tree is to use an enum or a trait. (Servo uses a trait for its flow tree, with downcast methods like as_block() if needed.)

I'm puzzled by the contention that the fact that all nodes have to be the same type is a problem with Rust. That's always true in any language. Even in C, you'd have to have your next/previous pointers have some type, or else you couldn't traverse the list!