Mutating a tree while performing a modified DFS without recursion

Question

I am trying to implement a modified version of a tree DFS without recursion and am struggling with the borrow checker. My requirement is that I want to ensure that child nodes are treated before their parent, and I would like all this to be mutable (no problem in the immutable case).

I have a simple tree structure as below:

struct Node {
    value: usize,
    children: Vec<Node>,
}

A normal iterative DFS might look like this (note that we are mutating the tree as we go):

fn normal_dfs(node: &mut Node) {
    let mut node_stack = vec![node];
    while !node_stack.is_empty() {
        let current_node = node_stack.pop().unwrap();
        for child_node in &mut current_node.children {
            node_stack.push(child_node);
        }

        current_node.value += 1;
    }
}

In the function above, parent nodes will be treated before their children, and I would like the opposite. I tried to build a stack of references to all the tree nodes, which I then plan to iterate backwards, ensuring that child nodes are treated before their parent:

fn modified_dfs(node: &mut Node) {
    //requirement: child nodes should be treated before parent nodes
    let mut node_stack = vec![node];
    let mut stack_index = 0usize;
    let mut stack_size = node_stack.len(); //not great but helps with borrow checker

    while stack_index < stack_size {
        let current_node = node_stack.get_mut(stack_index).unwrap();
        for child_node in &mut current_node.children {
            node_stack.push(child_node);
        }

        stack_size = node_stack.len();
        stack_index += 1;
    }

    //iterate stack in reverse to make sure child nodes are treated before parents
    for current_node in node_stack.iter_mut().rev() {
        current_node.value += 1;
    }
}

This doesn't compile with the error:

error[E0499]: cannot borrow `node_stack` as mutable more than once at a time
  --> src/lib.rs:13:28
   |
13 |         let current_node = node_stack.get_mut(stack_index).unwrap();
   |                            ^^^^^^^^^^ `node_stack` was mutably borrowed here in the previous iteration of the loop

error[E0499]: cannot borrow `node_stack` as mutable more than once at a time
  --> src/lib.rs:15:13
   |
13 |         let current_node = node_stack.get_mut(stack_index).unwrap();
   |                            ---------- first mutable borrow occurs here
14 |         for child_node in &mut current_node.children {
   |                           -------------------------- first borrow later used here
15 |             node_stack.push(child_node);
   |             ^^^^^^^^^^ second mutable borrow occurs here

error[E0502]: cannot borrow `node_stack` as immutable because it is also borrowed as mutable
  --> src/lib.rs:18:22
   |
13 |         let current_node = node_stack.get_mut(stack_index).unwrap();
   |                            ---------- mutable borrow occurs here
...
18 |         stack_size = node_stack.len();
   |                      ^^^^^^^^^^
   |                      |
   |                      immutable borrow occurs here
   |                      mutable borrow later used here

error[E0499]: cannot borrow `node_stack` as mutable more than once at a time
  --> src/lib.rs:23:25
   |
13 |         let current_node = node_stack.get_mut(stack_index).unwrap();
   |                            ---------- first mutable borrow occurs here
...
23 |     for current_node in node_stack.iter_mut().rev() {
   |                         ^^^^^^^^^^
   |                         |
   |                         second mutable borrow occurs here
   |                         first borrow later used here

I think I understand the reason for the error: I have borrowed the node_stack in an iteration, and the borrow is not "released" at the end of the iteration because child nodes have been put on the stack (it compiles if you don't push the child nodes).

What is an iterative algorithm to do this?

This may very well be one of the cases where Safe Rust is too limited. You may have to resort to `unsafe`, or, if you don't want to do that, use `RefCell`s to defer checking Rust's borrowing rules until runtime. — Lorenz, Mar 04 '20 at 15:04
It looks like your question might be answered by the answers of [Cannot obtain a mutable reference when iterating a recursive structure: cannot borrow as mutable more than once at a time](https://stackoverflow.com/q/37986640/155423); [Borrow pointer errors recursively traversing tree](https://stackoverflow.com/q/28767108/155423); [Implement graph-like data structure in Rust](https://stackoverflow.com/q/34747464/155423). If not, please **[edit]** your question to explain the differences. Otherwise, we can mark this question as already answered. — Shepmaster, May 06 '21 at 00:01
[How to make mutable pointer to field of node of tree and mutate it?](https://stackoverflow.com/q/37904071/155423) — Shepmaster, May 06 '21 at 00:01
[The duplicates applied to your situation](https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=0a2bf23b0ba23976dc9b13e32e3389f2) — Shepmaster, May 06 '21 at 00:11

score 3 · Answer 1 · answered May 10 '21 at 11:33

If you really have to do it mutably, you can use Rc and RefCell like this:

use std::cell::RefCell;
use std::rc::Rc;

struct Node {
    value: usize,
    children: Vec<Rc<RefCell<Node>>>,
}

fn modified_dfs(node: Rc<RefCell<Node>>) {
    //requirement: child nodes should be treated before parent nodes
    let mut node_stack = vec![node];
    let mut stack_index = 0usize;
    let mut stack_size = node_stack.len(); //not great but helps with borrow checker

    while stack_index < stack_size {
        let current_node = node_stack[stack_index].clone();
        for child_node in &current_node.borrow().children {
            {
                // Do something mutable with child_node
                child_node.borrow_mut();
            }
            node_stack.push(child_node.clone());
        }

        stack_size = node_stack.len();
        stack_index += 1;
    }

    //iterate stack in reverse to make sure child nodes are treated before parents
    for current_node in node_stack.iter_mut().rev() {
        current_node.borrow_mut().value += 1;
    }
}

Mutating a tree while performing a modified DFS without recursion

1 Answers1

Linked