Need help implementing a tree with stack based traversal

I'm tying to create a tree and initialize the tree by duplicating another tree with a stack.

but I ran into issues with Box, Rc and RefCell

both the Tree node and stack need to hold mutable ref to tree nodes.

I can't use Box due to single ownership. I can't use Rc, because I need mutability. How can I do it.

The following cpp code describes what I want to do. in the code, AnotherTree is from another library. I'm forced to use its tree traversal interface using a cursor.


struct Tree {
std::string name;
std::vector<Tree *> children;
};

Tree *root = new Tree();

std::vector<Tree*> stack;
stack.push_back(root);

TreeCursor cursor = AnotherTree.getCursor();

while (true) {
       Tree *node = new Tree(cursor);
       stack.last().children.push_back(node);
                
        if (cursor.goto_first_child()) {
            stack.push(node);
            continue;
        } else if (cursor.goto_next_sibling()) {
            continue;
        }

        bool retracing = true;
        while (retracing) {
            if (!cursor.goto_parent()) {
                retracing = false;
                reached_root = true;
            }
            else{
                stack.pop_back();
            }

            if (cursor.goto_next_sibling()) {
                retracing = false;
            }
        }
}

You can use both ref counting and interior mutability : Rc<RefCell<T>>

Learn Rust With Entirely Too Many Linked Lists

The simplest approach is to use the function call stack, so that the compiler can understand how the various references relate to each other:

struct Tree {
    name: String,
    children: Vec<Tree>
}

struct Cursor<'a>(&'a mut Tree);

impl<'a> Cursor<'a> {
    fn node(&mut self)->&mut Tree { unimplemented!() }
    fn goto_first_child(&mut self)->bool { unimplemented!() }
    fn goto_next_sibling(&mut self)->bool { unimplemented!() }
    fn goto_parent(&mut self)->bool { unimplemented!() }
}

impl Tree {
    pub fn from_cursor(cursor: &mut Cursor)->Self {
        let mut result = Tree {
            name: cursor.node().name.clone(),
            children: vec![]
        };
        
        if cursor.goto_first_child() {
            result.children.push(Tree::from_cursor(cursor));
            while cursor.goto_next_sibling() {
                result.children.push(Tree::from_cursor(cursor));
            }
            cursor.goto_parent();
        }
        
        result
    }
}

Thank you very much,

using Rc<RefCell> with

let last = stack.last().unwrap();
last.borrow_mut().children.push(c);

indeed solved my problem!