11. A linked or tree structure

The task

Build a tree of product categories, such as Books, then Fiction, then Crime. For any category, get its full path: "Books > Fiction > Crime".

In Java, each Category has a parent field and a List<Category> children, and the garbage collector handles the cycle. Rust has no garbage collector, so this task shows the difference clearly.

The versions

WorseThe Java object graph, translated: Rc<RefCell<Category>> up and down. It works, and the whole tree is never freed.

pub struct Category {
    pub name: String,
    pub parent: Option<Rc<RefCell<Category>>>, // a strong reference up...
    pub children: Vec<Rc<RefCell<Category>>>,  // ...and strong references down: a cycle
}

pub fn add_child(parent: &Rc<RefCell<Category>>, name: &str) -> Rc<RefCell<Category>> {
    let child = Rc::new(RefCell::new(Category {
        name: name.to_string(),
        parent: Some(Rc::clone(parent)),
        children: Vec::new(),
    }));
    parent.borrow_mut().children.push(Rc::clone(&child));
    child
}

pub fn path(category: &Rc<RefCell<Category>>) -> String {
    let mut names = vec![category.borrow().name.clone()];
    let mut current = category.borrow().parent.clone();
    while let Some(node) = current {
        names.push(node.borrow().name.clone());
        current = node.borrow().parent.clone();
    }
    names.reverse();
    names.join(" > ")
}

OKEach parent owns its children in a Vec. No parent links, so the path is found by a search from the root.

pub struct Category {
    pub name: String,
    pub children: Vec<Category>, // each child is owned by its parent
}

/// No parent links, so the path is found from the root down.
pub fn path(root: &Category, name: &str) -> Option<String> {
    if root.name == name {
        return Some(root.name.clone());
    }
    root.children
        .iter()
        .find_map(|child| path(child, name))
        .map(|rest| format!("{} > {rest}", root.name))
}

BetterAll categories in one Vec, and links are CategoryId indexes. Parent links are cheap, and there are no cycles.

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct CategoryId(usize);

pub struct Category {
    pub name: String,
    pub parent: Option<CategoryId>,
    pub children: Vec<CategoryId>,
}

/// All categories in one `Vec`. Links are indexes, so there are no cycles to leak.
#[derive(Default)]
pub struct Tree {
    nodes: Vec<Category>,
}

impl Tree {
    pub fn add(&mut self, name: &str, parent: Option<CategoryId>) -> CategoryId {
        let id = CategoryId(self.nodes.len());
        self.nodes.push(Category {
            name: name.to_string(),
            parent,
            children: Vec::new(),
        });
        if let Some(CategoryId(p)) = parent {
            self.nodes[p].children.push(id);
        }
        id
    }

    pub fn path(&self, id: CategoryId) -> String {
        let mut names = Vec::new();
        let mut current = Some(id);
        while let Some(CategoryId(i)) = current {
            names.push(self.nodes[i].name.as_str());
            current = self.nodes[i].parent;
        }
        names.reverse();
        names.join(" > ")
    }
}

The “Worse” version compiles, passes its functional test, and leaks memory. The parent holds an Rc to each child, and each child holds an Rc to its parent. The reference counts never reach zero, so no category is ever freed. The test worse_leaks_the_whole_tree drops the last outside handle to the root, and the root is still alive. See S35: Rc cycles (memory leak).

Even without the leak, the design has costs. Every access is .borrow() or .borrow_mut(), which is checked at run time and can panic. path clones each parent Rc to walk up the tree. See S03: Rc<RefCell<T>> object graph (Java translated directly).

The direct fix is to make the parent link a Weak (see Smart pointers). That stops the leak, but keeps the RefCell and adds upgrade() calls. The two versions below avoid shared pointers completely.

The “OK” version uses plain ownership: a parent owns its children, and a Vec already puts them on the heap. There are no Rc, no RefCell, and no possible leak. Without parent links, path cannot walk up. It searches from the root down, which is slower for a large tree, and it finds categories by name, not by identity.

The “Better” version is an arena: one Vec<Category> owns every node, and the links are indexes into it.

Links are Copy values. parent: Option<CategoryId> costs nothing to store or follow, and cannot form a cycle that leaks.
One owner. The Tree owns all nodes. When it is dropped, every node is freed.
No run-time borrow checks. add takes &mut self, path takes &self, and the compiler checks them.
CategoryId is a newtype with a private field, so code outside the module gets IDs only from add.

Verdict

Each version compared with the Worse version
Criterion	OK	Better
Correctness	Better	Better
"Worse" leaks the whole tree. "OK" finds a category by name, so two categories with the same name are ambiguous.
Failure behavior	Better	Better
"Worse" can panic on a `borrow_mut` conflict. "Better" cannot fail with IDs from its own `add`. An ID from another tree can panic, or point to the wrong node.
Performance	Same	Better
"Worse" does one allocation and reference count per node. "OK" walks the tree for each path. "Better" walks up with index lookups.
Readability	Better	Better
No `borrow()`, `clone()`, or `Rc` in the logic.
API ergonomics	Same	Better
"OK" is the simplest to build in a test. "Better" needs the `Tree` for every access, but gives stable IDs to store elsewhere.

Trade-offs

Removing nodes is harder in an arena. A removed index can be reused, and an old ID then points to the wrong node. If the tree changes often, use a crate made for this, such as slotmap, which detects old IDs. Check the crate on crates.io before you accept it in a review.
“OK” is the best choice for trees that are built once and read from the top: a parsed document, a configuration, a menu. Most trees in application code do not need parent links.
Rc with Weak parents is acceptable when nodes are shared with other code that must keep them alive, such as UI widgets. Then the Weak link is a requirement, not an option.
Rc<RefCell> in both directions is never correct for a tree. It always leaks.