Build tree paths with an arena and Rc

Implement two versions of the same operation, using the provided arena and Rc node structures:

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

parents[i] gives node i's parent index. Any negative value marks a root. Return one string per node, in index order, containing its root-to-node path with / separators. For example, [-1, 0, 1] produces ["0", "0/1", "0/1/2"]. Empty input produces an empty result.

Return "!" for a node whose parent chain never reaches a root. This includes an out-of-range parent, a cycle or self-loop, and any node whose chain leads into one of those invalid components. For [1, 0, 1], all three results are "!": node 2 leads into the cycle between nodes 0 and 1.

Both implementations must terminate on these inputs. Release the temporary graph's nodes on normal return, including nodes in cycles. The output checks alone cannot establish that memory was released.

Two ways to represent links

The arena keeps ArenaNode values in one vector and represents links with indices. The Rc version allocates individual Node values, with strong child links and weak parent links. Its RefCell fields allow links to be filled after node construction.

This exercise compares their ownership patterns. It does not establish that either representation is faster; that requires measurements for a specific workload.

Keep the arena's mutable borrows short

The starter holds a mutable reference to one indexed node while attempting another mutable indexed access, producing E0499. For this operation, you do not need both references at once.

This complete example performs the writes separately, even for a self-link:

struct Node {
    parent: Option<usize>,
    kids: Vec<usize>,
}

fn main() {
    let mut nodes = [Node { parent: None, kids: Vec::new() }];
    let i = 0;
    let p = 0;
    nodes[i].parent = Some(p);
    nodes[p].kids.push(i);
    assert_eq!(nodes[0].parent, Some(0));
    assert_eq!(nodes[0].kids, [0]);
}

Indices do not exempt an arena from borrowing rules. They let you choose when to borrow a node. When simultaneous access to different nodes is necessary, a splitting API can help. Here, sequential writes are sufficient, and p may equal i.

Walk down from roots in the arena

Build each valid parent's child list. Initialize every output to "!", then start a stack with all nodes whose parent value is negative. Give each root its own index as its path. When visiting a child, append its index to its parent's path.

Each node has only one parent entry, so a cycle cannot also be connected to a root. Neither cycles nor their descendants are reached by this traversal; their outputs remain "!". This reasoning depends on the input's single-parent structure, not on a general guarantee for arbitrary graphs.

The traversal visits each reachable node once. Creating the path strings also costs time and memory: a long chain repeats ancestor indices in many outputs, so the total output can be much larger than the node count.

Walk up through weak parents in the Rc version

Starting at each node, collect indices while following parent links. Limit the chain to at most the node count, or track visited indices, to detect cycles. If no parent link exists, check the original input: a negative parent denotes a root, but an out-of-range parent does not.

Keep RefCell guards short. A helper such as parent_of(&cur) can upgrade the weak parent and return an owned Rc, dropping the temporary borrow before you assign a new value to cur. Holding a guard across that assignment can cause E0506. At runtime, requesting a mutable borrow while the same cell is already borrowed can panic; recursion alone does not cause a borrow conflict.

The upward approach may repeat a long walk for many starting nodes. On a cycle, it can do quadratic work even though every output is just "!". Consider this algorithmic difference when comparing the two implementations.

Break strong cycles before returning

Weak parent links avoid the usual child-to-parent ownership cycle in a valid tree. They do not prevent arbitrary input from making a cycle entirely out of strong child links. For [1, 0], node 0 owns node 1 and node 1 owns node 0.

Once all paths are computed, clear every node's child list while the outer nodes vector still holds a strong handle to every node. This removes the strong edges. When that vector drops, the nodes can be released, including cyclic components and their descendants. Keeping all handles alive during cleanup also avoids recursively destroying a long child chain as you remove links.

This cleanup is for a temporary graph owned entirely by the function. A reusable graph needs an ownership and cycle policy appropriate to its API; it cannot silently discard links that callers still need.

Compare the actual costs

An arena is not automatically Clone or serializable just because it contains indices; those capabilities still need suitable implementations. Nor does an out-of-range index silently access memory: checked indexing panics, while get can report absence. Stale indices can still identify the wrong node if a different arena design removes or reuses slots.

Further reading: Rc and ownership cycles and RefCell borrowing.