Can't do breadth-first search on a binary tree in Rust

Question

I've implemented a binary tree in Rust as a learning project but failed to transverse it to print the tree in a breadth-first search fashion.

The issue is that I can't reassign the search queue (children) because it's borrowed and doesn't live long enough.

https://gist.github.com/varshard/3874803cd035e27facb67c59e89c3c1c#file-binary_tree-rs-L39

How can I correct this?

use std::fmt::Display;

type Branch<'a, T> = Option<Box<Node<'a, T>>>;

struct Node<'a, T: PartialOrd + Display> {
    value: &'a T,
    left: Branch<'a, T>,
    right: Branch<'a, T>
}

impl<'a, T: PartialOrd + Display> Node<'a, T> {
    fn insert(&mut self, value: &'a T) {
        let target_node = if value > self.value { &mut self.right } else { &mut self.left };
        match target_node {
            Some(ref mut node) => node.insert(value),
            None => {
                let new_node = Node{ value: value, left: None, right: None};
                *target_node = Some(Box::new(new_node))
            }
        }
    }
    fn display(&'a self) {
        let mut children: Vec<Option<&Node<'a, T>>> = Vec::new();
        children.push(Some(self));

        while children.len() > 0 {
            for child in &children {
                match child {
                    Some(node) => {
                        print!("{} ", node.value);
                    },
                    None => {
                        print!(" ")
                    }
                }
            }
            println!("");
            // Error: children doesn't live long enough;
            children = self.to_vec(&children);
        }
    }
    fn to_vec(&self, nodes: &'a Vec<Option<&Node<'a, T>>>) -> Vec<Option<&Node<'a, T>>> {
        let mut children: Vec<Option<&Node<'a, T>>> = Vec::new();
        for node_option in nodes {
            match node_option {
                Some(node) => {
                    match &node.left {
                        Some(left) => {
                            children.push(Some(left));
                            match &node.right {
                                Some(right) => {
                                    children.push(Some(right));
                                },
                                None => {
                                    children.push(None);
                                }
                            }
                        },
                        None => {
                            children.push(None);
                            match &node.right {
                                Some(right) => {
                                    children.push(Some(right));
                                },
                                None => {
                                    children.push(None);
                                }
                            }
                        }
                    }
                },
                None => {}
            }
        }

        children
    }
}

fn main() {
    let root_val = 5;
    let mut root = Node{ value: &root_val, left: None, right: None };
    root.insert(&3);
    root.insert(&4);
    root.insert(&1);
    root.insert(&6);

    root.display();
}

Answer 1

Copying my answer from this reddit comment:

There's a way to directly fix your problem, but I think there are better options for making the code easier to write and understand. For the direct fix, you can make some lifetime adjustments. Instead of

fn to_vec(&self, nodes: &'a Vec<Option<&Node<'a, T>>>) -> Vec<Option<&Node<'a, T>>> {

You need:

fn to_vec<'b>(&self, nodes: &Vec<Option<&'b Node<'a, T>>>) -> Vec<Option<&'b Node<'a, T>>>

What's the difference there? In the first case we're saying that nodes is a &'a Vec. That is, a borrow of a Vec that lives as long as the value references inside your tree. That's a long time to live, and it's what the compiler's getting angry about.

Now, if you just take the 'a off of that &Vec, the compiler complains about something else:

   |
42 |     fn to_vec(&self, nodes: &Vec<Option<&Node<'a, T>>>) -> Vec<Option<&Node<'a, T>>> {
   |                                         ------------       -------------------------
   |                                         |
   |                                         this parameter and the return type are declared with different lifetimes...
...
76 |         children
   |         ^^^^^^^^ ...but data from `nodes` is returned here

Maybe this is the error that pushed you to put the 'a on the &Vec in the first place. We need to solve it a different way. The important thing to understand here is that the return value doesn't contain references directly into the nodes vector, but it does contain copies of the nodes vector's contents, the &Node references. We need to tell the compiler that even though the nodes reference doesn't live very long, its contents do live longer. That's why we create the new lifetime 'b in my fix above.

This is objectively very confusing. Personally, I prefer to avoid solving these tricky problems, by just keeping things alive longer instead of reasoning about exactly how long they live. The source of the difficulty is that we're destroying the children vector on line 39. If we were able to keep it around, and just keep emptying it and refilling it, Rust would give us a much easier time. Have you considered using a std::collections::VecDeque instead of a Vec here? You could construct it once outside of your while-loop, and then you could pass &mut children around, without worrying very much about its lifetime. I think a queue is usually the go-to data structure for a breadth-first traversal, with new children added to the back, and the traversal itself reading from the front.