I very strongly disagree with this sentiment.
It's perfectly possible to write most useful data structures in entirely safe Rust, using the regular ownership and borrowing model, in a straightforward way, even as elegantly as it is possible to write other kind of Rust code.
Most of the problems pop up when one wants particular kinds of optimization that require clever trickery, owing to the internal invariants of a particular data structure. For example, one can easily write a doubly-linked list in Rust, provided you use Rc and Weak. If you insist on using the additional invariant that it's always a list, i.e. a node only ever points to the previous and next nodes, you can do it slightly more efficiently using unsafe, but it's not required. The same holds with regards to trees and general graph data structures as well.
In the light of this, let me provide an implementation (playground link) of OP's problem. Note @dv4512 that I have cleaned up the code:
- I have removed many redundant, unidiomatic parts (e.g. checking if a pointer is
Someimmediately followed by amapwhich does the same) - I have simplified the pretty-printing code, so that it actually outputs the tree in a visually correct form, albeit from left to right (rather than top to bottom). This aids debugging.
- I have removed everything except the solution of the problem, the pretty printing function, the construction of the tree, and the example in
main(). - I have renamed the types and functions so that they have more idiomatic names.
- I have introduced a generic type parameter into the tree node
struct, so you can abstract over any type in the future.
More importantly, my implementation contains zero unsafe , it has a time complexity of O(n) (it visits each node thrice) and a peak additional memory overhead of O(n) (the number of nodes in the last two levels times size_of::<&Node> , i.e., in practice a ~constant fraction of the memory required by the tree itself).
The insight is the following. When working with an algorithmic problem, the difficulty almost always arises because you are using the wrong kind of representation. The most elegant (and correct) implementations usually entail transforming the problem into a representation or "space" (so to say) where it's easy to solve, solving it there, and transforming the solution back. This is exactly what I have done here.
The problem as well as the solution requires operating on entire levels of the tree at once, which is quite an unnatural thing to do with a tree. The naturally-induced recursion structure on the tree is the depth-first traversal (ever wondered why DFS is so much simpler than BFS…?), and doing anything that breaks this pattern is going to cause pain. So, what I did consists of three steps:
- Transform the tree into a representation that favors explicit, flat levels over parent-child relationships. This required moving the nodes around, but that's not a big deal, because
Optionprovides thetake()method, so it's very natural to just remove child nodes from a parent node. This part of the algorithm is in thenodes_to_levels()function. - Once the tree is gone, and we have the flattened level data structure, it's trivial to reverse the order of nodes in every 2nd level.
- When we have the levels in the correct shape, we can transform the nodes back to the actual tree structure. For this, we take the nodes of each level, and add them, pairwise, as children to the nodes in the previous level. This requires us to maintain a list of pointers to nodes in the previous level.
If you run the code in the playground, you can see the tree before and after the transformation. For the sake of sparing space, I only paste the two relevant functions here:
impl<T> Node<T> {
fn invert_alternating_levels(&mut self) {
let mut map = BTreeMap::new();
self.nodes_to_levels(&mut map, 0);
// Traverse each level.
let mut prev_level = vec![self];
for (level, mut nodes) in map {
// Reverse every 2nd level
if level % 2 == 0 {
nodes.reverse();
}
// Transform back from flat level to parent-children relationships,
// by observing that for a perfect binary tree, level N+1 contains
// pairs of nodes which are the children of the respective nodes
// at the previous level, level N, and the correspondence is pairwise.
for (i, child) in nodes.into_iter().enumerate() {
if i % 2 == 0 {
prev_level[i / 2].left = Some(child);
} else {
prev_level[i / 2].right = Some(child);
}
}
// Update `prev_level` so that its new value is an array of pointers
// to the _children_ we just finished processing.
prev_level = prev_level
.into_iter()
.flat_map(|node| vec![
node.left.as_deref_mut().expect("missing left child: imperfect BST"),
node.right.as_deref_mut().expect("missing right child: imperfect BST"),
])
.collect();
}
}
/// Collects the subtrees into a map of levels: for each level (integer),
/// add, in the original left to right order, all nodes on that level.
fn nodes_to_levels(&mut self, map: &mut BTreeMap<usize, Vec<Box<Node<T>>>>, current: usize) {
// For both subtrees:
// * recurse into subtrees of children, i.e. fill the levels from bottom up,
// while we have ownership of the child
// * once that is done, we are ready to give up ownership of the child,
// adding it to the list representing the _current_ level
if let Some(mut left) = self.left.take() {
left.nodes_to_levels(map, current + 1);
map.entry(current).or_insert_with(Vec::new).push(left);
}
if let Some(mut right) = self.right.take() {
right.nodes_to_levels(map, current + 1);
map.entry(current).or_insert_with(Vec::new).push(right);
}
}
}