Attempting to implement a Tree using Rust

Hi everyone,

I recently learned of Rust and I'm very excited to be getting into it.

A friend of my was showing me how to implement a binary tree search in C++ so I figured I'd have a crack at it in Rust.

Would anyone mind to have a look at this code and give me some feedback?

struct Node<'a> {
    value: i8,
    lhs: Option<&'a Node<'a>>,
    rhs: Option<&'a Node<'a>>,
}

impl<'a> Node<'a> {
    fn new(value: i8) -> Node<'a> {
        Node {
            value,
            lhs: None,
            rhs: None,
        }
    }
}

struct Tree<'a> {
    root: &'a Node<'a>,
}

impl<'a> Tree<'a> {
    pub fn in_order(&self, node: &Option<&Node>) {
        match node {
            Some(n) => {
                println!("{}", n.value);

                match n.lhs {
                    Some(l) => self.in_order(&Some(l)),
                    None => return,
                };
                match n.rhs {
                    Some(r) => self.in_order(&Some(r)),
                    None => return,
                };
            }
            None => return,
        }
    }
}

pub fn run() {
    let mut root = Node::new(1);
    let a = &Node::new(2);
    root.lhs = Some(a);

    let b = Node::new(3);
    // root.rhs = Some(&b);
    root.lhs.lhs = Some(&b);
    // root.lhs.unwrap().rhs = Some(&Node::new(5));
    // root.rhs.unwrap().lhs = Some(&Node::new(6));
    // root.rhs.unwrap().lhs = Some(&Node::new(7));

    let tree = Tree { root: &root };
    let n = tree.in_order(&Some(&root));
    println!("N: {:?}", n);
}

Also I think in my friend's implementation in C++ he was able to assign child nodes to a node like so:

root.lhs.lhs.lhs.rhs = Node(value: 3)

As you can see in my code I ran into issues such as "creates a temporary which is freed while still in use" when doing something like this:

root.rhs = Some(&Node::new(3));

or

"no field lhs on type std::option::Option<&tree::Node<'_>>"
root.lhs.unwrap().lhs = Some(&b);

Any feedback would be great!

Cheers

Adam

References are meant to be temporary, and until you are familiar with the borrow checker, treat them that way. Don't use references here, use Box because the nodes need to be long lived.

struct Node {
    value: i8,
    lhs: Option<Box<Node>>,
    rhs: Option<Box<Node>>,
}
2 Likes

Thanks a lot! I’ll look into Box

there is an llrb implementation in rust https://github.com/bnclabs/llrb-index which is a self balancing binary tree.

This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.