Bake-off: the same tree, an arena and an `Rc` graph

One problem, two data structures, identical assertions.

pub fn tree_paths_arena(parents: Vec<i64>) -> Vec<String>
pub fn tree_paths_rc(parents: Vec<i64>) -> Vec<String>

parents[i] is the index of node i‘s parent, or a negative number if i is a root. Return, for every node in index order, the root-to-node path rendered with / — so a node reached as 0 → 2 → 5 renders as "0/2/5".

The input is not trusted. A node is "!" when it is not reachable from any root, which covers all three ways that can happen:

• its parent index is out of range,
• it sits below a node whose parent index is out of range,
• it sits on a cycle (parents = [1, 0] is two nodes and no roots).

A cyclic parents array would spin forever in the obvious implementation. Handle it. This is the one thing most submissions get wrong.

Why ship it twice

The previous items made an argument: for graph-shaped data, an index arena usually beats Rc<RefCell<_>>. Arguments are cheap. This item makes you write both, pass the same tests with both, and see the two shapes side by side.

(a) The arena. Every node in one Vec, links as usize. There are no references between nodes, so the borrow checker has nothing to object to. One allocation. Contiguous memory. Everything freed at once. Send, Clone, and serialisable, because it is made of integers.

(b) The Rc graph. Rc<Node> children pointing down, Weak<Node> parents pointing up, RefCell around each so the links can be patched after construction. One allocation per node, a refcount pair per node, a borrow flag per cell, and a walk that has to upgrade() at every step.

Both pass. Then look at the two functions and decide which one you would want to maintain, and which one you would want in a hot loop.

The compile error in the starter

let parent = &mut nodes[p];
nodes[i].parent = Some(p);
parent.kids.push(i);

error[E0499]: cannot borrow `nodes` as mutable more than once at a time

This is the arena error, and the one that sends people running back to Rc<RefCell<_>>. It is worth being precise about what it is telling you: you are holding an exclusive borrow of the whole Vec across a second exclusive borrow of the whole Vec. The compiler cannot see that p != i.

The fix is not a smart pointer. The fix is to stop holding the first borrow: do the two writes as two statements, each with its own short borrow. Once you internalise “index in, mutate, get out”, almost every arena borrow problem disappears — and the ones that do not are usually solved by split_at_mut or by making the operation take indices rather than references.

Two implementation notes

Walk down, not up, in the arena. Build a kids: Vec<usize> per node, seed a stack with every root, and assign each child’s path from its parent’s. That is one pass, and it makes the "!" rule free: whatever is never reached — cycles, orphans, everything under an orphan — keeps its initial "!".

Walking up in the Rc version needs care about guards. Two traps you have already met, in one loop:

• while let Some(p) = cur.parent.borrow().upgrade() fails to compile (E0506) because the Ref guard lives for the whole loop body and you want to reassign cur. Put the borrow in a helper function so the guard dies at the return.
• Holding a borrow() across a recursive call is the classic BorrowMutError in structures like this. It is the single most likely way to fail this problem at runtime rather than at compile time.

And when the walk reaches the top, ask whether you got there legitimately: a node whose parent index was out of range also has no parent link, so it looks like a root. Check the input to tell the two apart.

The costs, out loud

That last row is the whole case for Rc. If a node must be handed to something that has no idea the collection exists — a callback, a widget, a cache entry with an independent lifetime — the arena cannot express it and the Rc can.

And note the cycle row carefully in this problem. The arena version handles a cyclic parents array as a wrong answer and moves on. The Rc version builds a real cycle of strong kids links, and those nodes are never freed. Same input, same output, one of them leaks. Nothing warns you.