Tree traversal with indexed storage and shared locks

Compute the depth of every node in a rooted tree using two implementations, then check that their results agree.

pub fn tree_depths(edges: Vec<(usize, usize)>, threads: usize) -> Vec<usize>

Each edge is a (parent, child) pair. Node 0 is the root, with depth 0. Inputs describe a valid tree: node IDs are consecutive from 0 through the largest ID, every non-root node has one parent, and every node is reachable from the root. There are no duplicate edges, cycles or self-edges. Edge order need not be sorted, and a parent's ID need not be smaller than its child's ID.

Return depths indexed by node ID. An empty edge list represents only node 0 and returns [0]. Treat threads = 0 as one worker.

For edges [(0, 2), (2, 1), (2, 3)], return [0, 2, 1, 2]. Nodes 1 and 3 are both two edges away from the root.

Build and compare both versions

Keep two independent implementations:

1. A single-threaded breadth-first traversal using Vec<Vec<usize>> for child lists and a queue of node IDs. Do not use Rc, Arc, RefCell or locks in this version.
2. A level-by-level traversal with a mutex for each node, distributing each nonempty level across at most max(threads, 1) scoped workers.

Call both and assert that their depth vectors are equal before returning the result. Equality checks behavior; it does not establish which version is faster. The supplied arena traversal is complete. Repair the shared implementation and retain the comparison.

Why the starter cannot share its nodes

The starter uses Vec<Rc<RefCell<Node>>> and captures a shared reference to it in worker threads. That produces E0277: Rc is neither Send nor Sync, and RefCell is not Sync. The combination cannot support these shared cross-thread accesses.

These restrictions have different purposes. Rc's reference count is not synchronized. RefCell's borrow checks are also not synchronized and do not provide mutual exclusion between threads. RefCell<T> can nevertheless be moved to another thread when T is Send; moving sole ownership is different from sharing references concurrently.

Replacing only Rc with Arc is insufficient. Arc makes the reference count atomic, but does not make the contents safe for concurrent mutation.

Use the scope's lifetime guarantee

Here Vec<Mutex<Node>> is enough. The vector remains alive until all scoped threads have joined, so workers can borrow it. There is no need for a separate Arc allocation per node.

Arc<Mutex<T>> is useful when owners need independently retained handles, provided T satisfies the required Send bound. Scoped borrowing is an alternative when one owner can keep the data alive for all workers.

Traverse one level at a time

Each frontier contains node IDs at the same depth. Split it into nonempty chunks and let each worker process one chunk. A narrow level may use fewer workers than requested. This implementation creates scoped workers per level, rather than keeping a persistent worker pool.

For each node, lock it long enough to read its depth and copy its child IDs. Release that guard before locking any child. Then assign each child's depth and collect its ID in the worker's next-frontier list.

Merge those lists, join every worker, then start the next level. The tree contract ensures each child has exactly one parent. A general graph would need additional handling for repeated visits and cycles.

Sorting the next frontier makes processing order deterministic, although output order comes from indexing the final depth vector by node ID. Avoid retaining a node lock while acquiring another node's lock; the short guard scopes here avoid that lock-ordering problem.

Compare ownership needs, not slogans

Rc<RefCell<T>> supports shared mutable state within one thread. Conflicting borrows can panic through borrow_mut; try_borrow_mut reports a conflict instead. Retained strong cycles can leak values, while weak back-references can avoid keeping a parent alive. Upgrading such a Weak may return None when the parent has already been released.

Mutex provides exclusive access across threads when its type bounds allow that sharing. Locks can block, and poisoning is reported as a Result. This exercise uses expect, so a poisoning error becomes a panic. Wrapping a graph in Arc and Mutex does not by itself prevent ownership cycles or deadlocks.

Indexed storage puts lifetime management under one owner. Child IDs do not retain nodes, so cyclic index links would not create a reference-count leak, though traversal would still need cycle handling. The outer vector stores child-list headers contiguously; each list has its own buffer.

An index also needs a validity policy. An out-of-range index panics with ordinary indexing; an in-range index from the wrong arena may select the wrong node. Generations help detect stale reused slots, but do not alone establish which arena an index belongs to.

Parallelism still requires correct access partitioning or synchronization. Indices alone do not prove that two workers access different nodes. Measure performance for a relevant workload before preferring one design on speed grounds.

The submission must compile, match the depths, retain both implementations and their assertion, and pass Clippy with warnings denied.