In Rust, how do you make for v in &tree walk a binary tree in order, and why must the walker carry a lifetime?
answer
- a for loop wants IntoIterator
- implement it for &'a Tree<T>
- a stack of node references
- Item borrows from the tree
- iter, iter_mut, into_iter
basics
~20 sImplement IntoIterator for &'a Tree<T> with Item = &'a T and IntoIter = Iter<'a, T>, a walker holding a stack of &'a Node<T>. The lifetime ties each yielded reference to the tree, not the walker, so callers can keep them.
solid answer
~40 s`for v in &tree` calls `IntoIterator::into_iter(&tree)`, so without an impl rustc reports E0277, "`&Tree<{integer}>` is not an iterator". Write a walker `struct Iter<'a, T> { stack: Vec<&'a Node<T>> }` whose `next` pops a node, pushes the left spine of its right child and returns `&'a T`; add `fn iter(&self) -> Iter<'_, T>` and `impl<'a, T> IntoIterator for &'a Tree<T>` with `type Item = &'a T` and `type IntoIter = Iter<'a, T>`. The walker is a separate type because iterating needs state the tree must not carry, and because `Item` must name a lifetime: `Iterator::Item` has no lifetime parameter, so `type Item = &T` is rejected unless the lifetime comes from the implementing type. Here it comes from the tree, so `tree.iter().max()` and collected references outlive the walker.
code
rust · 53 linesstruct Node<T> { val: T, left: Option<Box<Node<T>>>, right: Option<Box<Node<T>>> }
struct Tree<T> { root: Option<Box<Node<T>>> }
/// In-order walker: a stack of nodes whose left side is already pushed.
struct Iter<'a, T> { stack: Vec<&'a Node<T>> }
impl<'a, T> Iter<'a, T> {
fn push_left(&mut self, mut node: Option<&'a Node<T>>) {
while let Some(n) = node {
self.stack.push(n);
node = n.left.as_deref();
}
}
}
impl<'a, T> Iterator for Iter<'a, T> {
type Item = &'a T;
fn next(&mut self) -> Option<&'a T> {
let n = self.stack.pop()?;
self.push_left(n.right.as_deref());
Some(&n.val)
}
}
impl<T> Tree<T> {
fn iter(&self) -> Iter<'_, T> {
let mut it = Iter { stack: Vec::new() };
it.push_left(self.root.as_deref());
it
}
}
impl<'a, T> IntoIterator for &'a Tree<T> {
type Item = &'a T;
type IntoIter = Iter<'a, T>;
fn into_iter(self) -> Iter<'a, T> {
self.iter()
}
}
fn leaf<T>(val: T) -> Option<Box<Node<T>>> {
Some(Box::new(Node { val, left: None, right: None }))
}
fn main() {
let tree = Tree { root: Some(Box::new(Node { val: 5, left: leaf(2), right: leaf(9) })) };
for v in &tree {
print!("{v} ");
}
println!();
let max = tree.iter().max();
println!("{max:?} and the tree is still usable: {}", tree.iter().count());
}go deeper
Know that for v in &collection needs IntoIterator for the reference type, and the iter, iter_mut and into_iter naming convention.
Write the walker struct with a lifetime, the IntoIterator impl for &'a Tree<T>, and explain the explicit stack for an in-order walk.
Explain why Item cannot borrow from the walker itself, why the items outlive it, and what makes iter_mut and the by-value form harder.
Choose which of the three iteration forms a collection exposes publicly, since each IntoIterator impl and iterator type becomes API callers rely on.
## What the for loop asks for A `for` loop is sugar over the `IntoIterator` trait: `for v in expr` calls `IntoIterator::into_iter(expr)` and then `next` until `None`. Writing `for v in &tree` therefore needs `IntoIterator` implemented for the **reference type** `&Tree<T>`. Without it, rustc 1.99 reports E0277, "`&Tree<{integer}>` is not an iterator", with the note that `Iterator` would be required for `&Tree` to implement `IntoIterator`. std's collections follow one convention, which the Rust API Guidelines write down as C-ITER and C-ITER-TY: | Method | Item | Iterator type | `IntoIterator` impl | |---|---|---|---| | `iter(&self)` | `&T` | `Iter<'a, T>` | `for &'a Tree<T>` | | `iter_mut(&mut self)` | `&mut T` | `IterMut<'a, T>` | `for &'a mut Tree<T>` | | `into_iter(self)` | `T` | `IntoIter<T>` | `for Tree<T>` | The reference impls are what make the collection pleasant to pass around: a function written once over `impl IntoIterator<Item = &'a T>` accepts `&vec`, `&tree` or a slice alike, and the caller keeps ownership of the collection. Following the convention means `for v in &tree`, `tree.iter()` and passing `&tree` to a function taking `impl IntoIterator<Item = &i32>` all work. ## The in-order walker An in-order walk visits the left subtree, the node, then the right subtree. Recursion cannot pause between items, so the iterator keeps an explicit **stack** of nodes whose left side has already been pushed: ```rust struct Iter<'a, T> { stack: Vec<&'a Node<T>> } impl<'a, T> Iterator for Iter<'a, T> { type Item = &'a T; fn next(&mut self) -> Option<&'a T> { let n = self.stack.pop()?; self.push_left(n.right.as_deref()); Some(&n.val) } } ``` 1. `Tree::iter` creates the walker and pushes the root's **left spine** — the root, its left child, that child's left child, and so on. 2. Each `next` pops the top node, which is the smallest unvisited value. 3. Before returning it, `next` pushes the left spine of that node's right child, so the successor is on top for the next call. Each node is pushed and popped once, so a full walk is linear in the number of nodes, and the stack holds at most one path from root to leaf — memory proportional to the tree's height. `Option<Box<Node<T>>>::as_deref()` turns a child into an `Option<&Node<T>>` without moving it out of the tree. ## Why a separate struct, and why the lifetime - **State does not belong in the tree.** The stack is per walk; two walks over the same tree at once, or a walk while another part of the program reads the tree, must not share it. A `&Tree` cannot be mutated to hold it anyway. - **`Item` must name a lifetime.** `Iterator` declares `type Item;` with no lifetime parameter, so `impl<'a, T> Iterator for Iter<'a, T> { type Item = &T; ... }` is rejected: rustc says the associated type is declared without lifetime parameters, so a borrowed type must take its lifetime from the implemented type, and suggests a new type that borrows the existing one. The struct's `'a` is that lifetime. - **The items outlive the walker.** Because `Item = &'a T` borrows from the tree, not from the walker's `&mut self`, callers can keep the references: `tree.iter().max()` returns an `Option<&T>` after the walker is gone, and `collect::<Vec<&T>>()` works. An iterator that lends items borrowing from itself is a different design, covered with generic associated types. ## The IntoIterator impl ```rust impl<'a, T> IntoIterator for &'a Tree<T> { type Item = &'a T; type IntoIter = Iter<'a, T>; fn into_iter(self) -> Iter<'a, T> { self.iter() } } ``` `IntoIter` must be a type you can name, which is one reason the walker is a struct rather than a closure-built `impl Iterator`. Because the impl is on a reference, iterating leaves the tree usable afterwards. ## Going further - **`iter_mut` is harder.** A stack of `&'a mut Node<T>` must hand out `&mut val` while keeping a separate `&mut` to the right child, which takes splitting the node's borrows field by field. - **By-value `IntoIterator for Tree<T>`** yields `T` and keeps a stack of owned `Box<Node<T>>`, taking children out as it goes. - **Extra traits.** The walker returns `None` forever once its stack is empty, so `impl FusedIterator` is honest; tracking a remaining count would allow an exact `size_hint`.
- Why is the walker's memory proportional to the tree's height rather than its size?The stack only holds the left spine still to visit along one root-to-leaf path. Each pop pushes at most the left spine of one right child, so the stack never exceeds the tree's height, while each node is still pushed and popped exactly once overall.
- Why must IntoIterator::IntoIter be a named type here instead of a closure-built iterator?An associated type in a trait impl must be written out, and a closure's type has no name, so `type IntoIter = ...` cannot refer to an `iter::from_fn` iterator on stable Rust. A named walker struct is the stable way to fill it.
- for v in &tree works once Tree implements Iterator itself.
- type Item = &T is fine because elision infers the lifetime.
- The yielded references die when the walker is dropped.
- An in-order walk needs a stack as large as the whole tree.
- IntoIter can be any impl Iterator without naming a type.