Traversing lazily-growing tree


I’ve got infinitely-large tree which I need to traverse in specific order (like in A*). The tree has to be built lazily, and there needs to be a queue for nodes yet to be traversed, and this creates a tricky case that I don’t think RefCell can solve.

  • The tree is infinitely large, so I have to create nodes lazily. I could use RefCell for that, but
  • I need to store nodes to be traversed in BinaryHeap queue, so lifetime of RefCell borrow is too short for that
  • Creation of nodes is very expensive, and I have to conserve memory, so I can’t use solutions that clone/recreate nodes on the fly.

I’ve tried:

struct Node {
    children: RefCell<Option<(&Node, &Node)>>;

impl Node {
    fn traverse(&self, queue: &mut BinaryHeap) {
        if nodes not created {
           // Mutably create here

while let Some(node) = queue.pop() {
    traverse(node, &mut queue);

How can I make it work?


Does the usual solution of storing nodes in a single Vec and using indices in children and queue work?


Hm, I think there is an even simpler solution. You can implement a LazyCell, which is a write once RefCell without Ref:


Thank you for suggestions.

The Vec solution would work for me currently, but long term I hoped to be also able to prune items from the tree, and then I’d end up with a compacting GC in a Vec :wink:

LazyCell looks perfect!


You could also just use Rc.