How to solve "returns a value referencing data owned by the current function" error in Rust?

I'm trying to code a binary tree that generates random expressions. I need random numbers and a set of functions. I receive a vector with the functions and the depth for the expression in the tree. In the operators vector, I also include a "ELEM" string, this is used to choose a random element from the vector and then change it for a float.

It seems I still do not understand the exact use for borrows, moving and ownership, since it is a recursive function, it shows the error saying that value has been borrowed and cannot return a local variable.

use rand::Rng;

struct Expression_Node {
    val: &'a str,
    left: Option>>,
    right: Option>>,
}

fn Create_Expression(
    operators: Vec,
    p: i32,
) -> std::option::Option>> {
    if p == 0 {
        let value = String::from(rand::thread_rng().gen::().to_string());
        let value2: &str = value.as_ref();
        //println!("{:?}", value);
        let new_node = Expression_Node {
            val: value2,
            left: None,
            right: None,
        };
        return Some(Box::new(new_node));
    }
    let value: &str = *rand::thread_rng().choose(&operators).unwrap();
    println!("VAL: {:?}", value);
    if value == "ELEM" {
        let value = rand::thread_rng().gen::().to_string();
    }

    let new_node = Expression_Node {
        val: value,
        left: Create_Expression(operators.clone(), p - 1),
        right: Create_Expression(operators.clone(), p - 1),
    };
    return Some(Box::new(new_node));
}

The error:

error[E0515]: cannot return value referencing local variable value
--> src/lib.rs:22:16
|
15 | let value2: &str = value.as_ref();
| ----- value is borrowed here
...
22 | return Some(Box::new(new_node));
| ^^^^^^^^^^^^^^^^^^^^^^^^ returns a value referencing data owned by the current function


The biggest problem with the code is the use of &str in the ExpressionNode.
The simplest fix is to change it to String. You can see the fix for that below.
This also allows removal of all the lifetime annotations.

There's also a second fix in that code that is important.

let value: &str = *rand::thread_rng().choose(&operators).unwrap();
if value == "ELEM"{
    let value = rand::thread_rng().gen::().to_string();
}

should be updating value, so the assignment within the if should not contain let, and the first assignment should be let mut value.

If you're not happy with all the assignments that are happening when switching to a String, you have two other options - use a Cow string or use a enum for the contained value type so that it can contain a string or a float, something like - val: Either (There's a version using this at the end of this answer).

The string based version:

use rand::Rng;

#[derive(Debug)]
struct ExpressionNode {
    val: String,
    left: Option>,
    right: Option>,
}

fn create_expression(operators: &[&str], p: i32) -> Option> {
    if p == 0 {
        let value = String::from(rand::thread_rng().gen::().to_string());
        let new_node = ExpressionNode {
            val: value,
            left: None,
            right: None,
        };
        return Some(Box::new(new_node));
    }
    let mut value = rand::thread_rng().choose(&operators).unwrap().to_string();
    if value == "ELEM" {
        value = rand::thread_rng().gen::().to_string();
    }

    let new_node = ExpressionNode {
        val: value,
        left: create_expression(operators.clone(), p - 1),
        right: create_expression(operators.clone(), p - 1),
    };
    Some(Box::new(new_node))
}

fn main() {
    let v = vec!["a", "b", "c", "ELEM"];
    let tree = create_expression(&v, 3);
    println!("tree = {:?}", tree)
}

For comparison, here's a version using Either:

use either::Either;
use rand::Rng;

#[derive(Debug)]
struct ExpressionNode {
    val: Either,
    left: Option>>,
    right: Option>>,
}

fn create_expression(operators: &[&'a str], p: i32) -> Option>> {
    if p == 0 {
        let value = rand::thread_rng().gen::();
        let new_node = ExpressionNode {
            val: Either::Right(value),
            left: None,
            right: None,
        };
        return Some(Box::new(new_node));
    }
    let v = *rand::thread_rng().choose(&operators).unwrap();
    let value = if v == "ELEM" {
        Either::Right(rand::thread_rng().gen::())
    } else {
        Either::Left(v)
    };

    let new_node = ExpressionNode {
        val: value,
        left: create_expression(operators.clone(), p - 1),
        right: create_expression(operators.clone(), p - 1),
    };
    Some(Box::new(new_node))
}

fn main() {
    let v = vec!["a", "b", "c", "ELEM"];
    let tree = create_expression(&v, 3);
    println!("tree = {:?}", tree)
}

Stack Overflow Q#54758052, score: 19