Attempting to implement a Tree using Rust

[adamteale]

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

[RustyYato]

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>>,
}

[adamteale]

Thanks a lot! I’ll look into Box

[prataprc]

there is an llrb implementation in rust GitHub - bnclabs/llrb-index: Left Leaning Red Black Tree in Rust. which is a self balancing binary tree.