Would Rust be the best choice of language, given all the back pointers (previous, parent)?

Trees are not that bad in Rust, it's when you have a cyclical structure that Rust is really difficult.

Yes, that's what I meant by "back pointers". In the article, every node has a parent pointer and a child pointer (or several). You can't have both of these pointers without introducing cycles.