How to efficiently compute depth of generated tree

⚓ rust    📅 2025-06-14    👤 surdeus    👁️ 4      

surdeus

Warning

This post was published 35 days ago. The information described in this article may have changed.

Hello :waving_hand: , I'm new to rust so I'm trying to implement some interesting problem I already have in another language. But i keep running into problems with the borrow system. In particular I have this virtual tree, generated from the root that has type System<'a>.

System (click for more details)

In particular, env and rules are shared by all members, set and process instead are unique for each node.

The first problem i have is that i would like to know the depth of the tree. Since i know that its perfectly balanced, it is enough to check the depth of the leftmost leaf.

fn depth<'a>(system: &'a System<'a>) -> Result<i64, String> {
    let current =
	match one_transition(system)? {
	    Some((_, system)) => system,
	    None => return Ok(0),
	};
    Ok(depth(&current)? + 1)
}

The function one_transition simply follows the leftmost branch and has signature:

fn one_transition<'a>(system: &'a System<'a>) -> Result<Option<(Label<'a>, System<'a>)>, String>

where the label is metadata about the transition so its ignored in this case. The computation may fail so its wrapped in a Result, if there is a next node we return Some(...) otherwise we return None.

The problem with the function depth is that it keeps in memory all previous nodes until we have found the last one. I would like to rewrite it in a more imperative style like:

fn depth<'a>(system: &'a System<'a>) -> Result<i64, String> {
    let current = one_transition(system)?;
    if current.is_none() {
        return Ok(0);
    }
    let mut n = 1;
    let mut current = current.unwrap().1;
    while let Some((_, next)) = one_transition(&current)? {
        current = next; // incriminating line
        n += 1;
    }
    Ok(n)
}

except that it doesn't work since current is dropped. Cloning doesn't seem to help.

The second problem is if i need to return some information about the last element the compiler keeps again complaining about lifetimes and how i cant clone stuff. But solving the first problem probably solves the second too.

12 posts - 3 participants

Read full topic

🏷️ rust_feed