💾 Archived View for danieljanus.pl › blog › en › 2023 › 07 › 16 › iterating-trees › index.gmi captured on 2024-05-26 at 14:32:35. Gemini links have been rewritten to link to archived content

-=-=-=-=-=-=-

A visual tree iterator in Rust

My adventure with learning Rust [1] continues. As a quick recap from the previous post, I’m writing a tree viewer [2]. I have now completed another major milestone, which is to rewrite the tree-printing function to use an iterator. (Rationale: it makes the code more reusable – I can, for instance, easily implement a tree-drawing view for Cursive [3] with it.)

And, as usual, I’ve fallen into many traps before arriving at a working version. In this post, I’ll reflect on the mistakes I’ve made.

The problem

Let’s start with establishing the problem. Given a “Tree” struct defined as:

pub struct Tree<T> {
    value: T,
    children: Vec<Tree<T>>,
}

I want it to have a “lines()” method returning an iterator, so that I can implement “print_tree” as:

fn print_tree<T: Display>(t: &Tree<T>) {
    for line in t.lines() {
        println!("{}", line);
    }
}

and have the output identical to the previous version.

The algorithm

Before we dive into the iterator sea, let’s have a look at the algorithm. Imagine that we’re printing the tree (in sexp-notation) “(root (one (two) (three (four))) (five (six)))”. This is its dissected visual representation:

Anatomy of a tree

Each line consists of three concatenated elements, which I call “parent prefix”, “immediate prefix”, and “node value”. The immediate prefix is always (except for the root node) “"└─ "” or “"├─ "”, depending on whether the node in question is the last child of its parent or not. The parent prefix has variable length that depends on the node’s depth, and has the following properties:

For any node, all its subnodes’ parent prefixes start with its parent prefix.
For any node, the parent prefixes of its direct children are obtained by appending “" "” or “"│ "” to its own parent prefix, again depending on whether the node is its parent’s last child or not.

This gives rise to the following algorithm that calls itself recursively. In pseudo-Python:

def print_tree(node, parent_prefix, parent_suffix, immediate_prefix):
    println(parent_prefix, immediate_prefix, node)
    for child in node.children:
        if child.is_last():
            print_tree(child, parent_prefix + parent_suffix, "   ", "└─ ")
        else:
            print_tree(child, parent_prefix + parent_suffix, "│  ", "├─ ")

Links

[1]

[2]

[3]