Skip to content
TheChatArchiveThe Chat Archive
gpt-4.1-mini-2025-04-14· OpenAIHugging Face LMArena Human Preference 140K

Implement a generic tree data structure in Rust.

From a Chatbot Arena battleThe same person sent this prompt to two anonymous models at once. Compare it with Claudeclaude-3-5-sonnet-20241022’s answer.
  1. User

    Implement a generic tree data structure in Rust.

  2. Assistant

    Certainly! Below is a simple implementation of a generic tree data structure in Rust. This example uses Rc and RefCell to allow multiple ownership and interior mutability, which is common for tree structures where nodes can have multiple children and you want to mutate the tree after creation.

    use std::cell::RefCell;
    use std::rc::{Rc, Weak};
    
    type NodeRef<T> = Rc<RefCell<TreeNode<T>>>;
    
    #[derive(Debug)]
    pub struct TreeNode<T> {
        pub value: T,
        pub parent: Option<Weak<RefCell<TreeNode<T>>>>,
        pub children: Vec<NodeRef<T>>,
    }
    
    impl<T> TreeNode<T> {
        pub fn new(value: T) -> NodeRef<T> {
            Rc::new(RefCell::new(TreeNode {
                value,
                parent: None,
                children: vec![],
            }))
        }
    
        pub fn add_child(parent: &NodeRef<T>, child_value: T) -> NodeRef<T> {
            let child = TreeNode::new(child_value);
            child.borrow_mut().parent = Some(Rc::downgrade(parent));
            parent.borrow_mut().children.push(Rc::clone(&child));
            child
        }
    
        pub fn parent(node: &NodeRef<T>) -> Option<NodeRef<T>> {
            node.borrow()
                .parent
                .as_ref()
                .and_then(|weak_parent| weak_parent.upgrade())
        }
    
        pub fn children(node: &NodeRef<T>) -> Vec<NodeRef<T>> {
            node.borrow().children.clone()
        }
    }
    
    fn main() {
        // Example usage:
        let root = TreeNode::new("root");
        let child1 = TreeNode::add_child(&root, "child1");
        let child2 = TreeNode::add_child(&root, "child2");
        let grandchild = TreeNode::add_child(&child1, "grandchild");
    
        println!("Root: {:?}", root.borrow().value);
        println!("Children of root:");
        for child in TreeNode::children(&root) {
            println!(" - {}", child.borrow().value);
        }
    
        if let Some(parent) = TreeNode::parent(&grandchild) {
            println!("Parent of grandchild: {}", parent.borrow().value);
        }
    }
    

    Explanation:

    • TreeNode<T> holds a value of generic type T.
    • Each node has a parent which is a Weak reference to avoid reference cycles.
    • Each node has a vector of children which are Rc<RefCell<TreeNode<T>>>.
    • new creates a new node with no parent and no children.
    • add_child adds a child to a parent node, setting the child's parent pointer.
    • parent returns an Option<NodeRef<T>> to the parent node if it exists.
    • children returns a vector of children nodes.

    This structure allows you to build and traverse a generic tree with parent and child relationships. Let me know if you want traversal methods or other features!

Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.