Crate arboriter 

arboriter: Tree Traversal Primitives for Rust

The arboriter crate provides a tree traversal primitive similar to a for loop but designed specifically for traversing tree-like structures without explicit recursion.

Inspired by Tyler Glaiel’s blog post discussing the need for such a primitive, this crate implements a for_tree! macro that brings the convenience of standard control flow constructs to tree traversal operations.

Features

• Intuitive Syntax: Similar to a for loop, familiar to most programmers
• Control Flow: Support for break, continue, and a special prune! operation
• Flexible: Works with both in-memory tree structures and imperative tree generation
• Type Safe: Fully leverages Rust’s type system for safety and clarity
• Zero Cost: Compiles to efficient code equivalent to hand-written recursion

Quick Example

use arboriter::{for_tree, prune, break_tree, BinaryNode};

// Create a simple binary tree
let root = BinaryNode::with_children(
    1,
    Some(Box::new(BinaryNode::new(2))),
    Some(Box::new(BinaryNode::new(3)))
);

// Traverse the tree
for_tree!(node in &root; |_| true; |node| {
    let mut children: Vec<&BinaryNode<i32>> = Vec::new();
    if let Some(left) = &node.left {
        children.push(left.as_ref());
    }
    if let Some(right) = &node.right {
        children.push(right.as_ref());
    }
    children
} => {
    println!("Value: {}", node.value);
});

Usage

The for_tree! macro syntax is designed to be reminiscent of a standard for loop:

for_tree!(variable in initial_value; condition; branches => {
    // body
    // You can use special control flow:
    // - break_tree!(); - exits the entire traversal
    // - prune!(); - skips traversing children of the current node
});

Where:

• variable is the name of the variable for the current node
• initial_value is the starting node
• condition is a closure that determines if a node should be visited
• branches is a closure that returns a vector of child nodes
• body is the code executed for each node

Advanced Example: String Generation

The for_tree! macro isn’t limited to traversing existing data structures; it can also be used to generate tree-like data:

use arboriter::{for_tree, prune};

// Generate all strings of 'a' and 'b' with length <= 2
let mut strings = Vec::new();

for_tree!(s in String::new(); |s| s.len() <= 2; |s| {
    let mut branches: Vec<String> = Vec::new();
    branches.push(format!("{}a", s));
    branches.push(format!("{}b", s));
    branches
} => {
    strings.push(s.clone());

    if s.len() == 2 {
        prune!(); // Don't generate longer strings
    }
});

// Strings in depth-first order: ["", "a", "aa", "ab", "b", "ba", "bb"]
assert_eq!(strings, vec!["", "a", "aa", "ab", "b", "ba", "bb"]);

Control Flow

The for_tree! macro supports special control flow operations:

• continue - Standard Rust continue, skip to the next iteration
• prune!() - Skip traversing children of the current node
• break_tree!() - Exit the entire traversal (unwinding the recursion stack)

Performance

The for_tree! macro is a zero-cost abstraction - it compiles down to efficient recursive code and introduces no runtime overhead compared to hand-written recursive traversal functions.

Macros

break_tree

Breaks out of the entire tree traversal.

for_tree

A macro for traversing tree-like structures or generating tree-like data.

prune

Skips traversing the children of the current node.

Structs

BinaryNode

Tree node example for binary trees

Enums

TreeControl

Enum representing control flow options within a tree traversal.

Functions

binary_tree_example

Demonstrates traversing a binary tree with the for_tree macro.

generate_strings_example

Demonstrates using for_tree for string generation.

traverse_tree

Core function that handles depth-first tree traversal of arbitrary tree-like structures.