The Stack-Allocated Linked List

Recursion already builds a linked list. Each call frame holds locals and a return address pointing at the caller's frame. If you also pass a &Frame parameter pointing at the caller's data, the chain of frames is a linked list of nodes living on the program stack — no heap, no Box, no Drop problem.

1. 01
   A node is a value plus an optional reference to the previous node. The lifetime 'a ties it to the parent frame's node. Option<&'a Frame<'a, T>> is one pointer wide and lives entirely in registers or stack slots.

   struct Frame<'a, T> {
       elem: T,
       parent: Option<&'a Frame<'a, T>>,
   }
   
   impl<'a, T> Frame<'a, T> {
       fn iter(&self) -> Iter<'_, T> {
           Iter { node: Some(self) }
       }
   }

2. 02
   The walker takes the parent frame's node by reference and constructs its own node on its own stack frame. Recurse with Some(&me). When the call returns, me is gone — and so is its node, automatically.

   fn walk<'a, T: std::fmt::Debug>(
       tree: &Tree<T>,
       parent: Option<&'a Frame<'a, &'a T>>,
   ) {
       let me = Frame { elem: &tree.value, parent };
   
       if tree.children.is_empty() {
           // at a leaf — print the path from root to here
           let path: Vec<_> = me.iter().collect();
           println!("{:?}", path.into_iter().rev().collect::<Vec<_>>());
       }
   
       for child in &tree.children {
           walk(child, Some(&me));
       }
   }

3. 03
   The iterator follows parent links upward. Yields &T from each frame. Iter itself is one pointer; the entire path lives on the stack and is visible to the leaf without ever copying or allocating.

   struct Iter<'a, T> {
       node: Option<&'a Frame<'a, T>>,
   }
   
   impl<'a, T> Iterator for Iter<'a, T> {
       type Item = &'a T;
       fn next(&mut self) -> Option<&'a T> {
           let n = self.node?;
           self.node = n.parent;
           Some(&n.elem)
       }
   }