Trait tree_iterators_rs::prelude::TreeIterator

pub trait TreeIterator: Iterator {
    // Required methods
    fn leaves(self) -> impl LeavesIterator<Item = Self::Item>;
    fn attach_ancestors(self) -> impl AncestorsIterator<Item = [Self::Item]>;
}

this trait provides a consistent trait to simplify this library’s public interface and documentation.

Required Methods

fn leaves(self) -> impl LeavesIterator<Item = Self::Item>

This method converts the current iterator into an iterator that will yield only the leaves of the tree. Iteration still proceeds in either a breadth first search (if called on a breadth first iterator) or depth first post-order search (if called on a depth first pre-, in-, or post-order iterator). This method is safe to call at any point during iteration and will never panic.

A leaf is defined as: Any tree node that has no children. Given a tree of the following shape, this iterator would always yield values in the following order (regardless of iteration type): 3, 4, 5, 10

       0
      / \
     1   2
    / \ / \
   3  4 5  6
          /
         7
          \
           8
          /
         9
          \
          10

// Example usage:
use tree_iterators_rs::{
    prelude::*,
    examples::create_example_binary_tree
};

let root = create_example_binary_tree();
for leaf in root.bfs_iter().leaves() {
    println!("{}", leaf);
}

fn attach_ancestors(self) -> impl AncestorsIterator<Item = [Self::Item]>

This method will panic if called after an element has already been yielded from the iterator it is called on!

This method attaches the ancestors of each node to it during iteration. This operation converts the current iterator into a streaming iterator.

For Breadth First Search iterators, this converts the queue-based iterator into an iterative deepening iterator. This can have performance impacts, as iterative deepening visits many nodes in the tree more than once.

For Depth First Search iterators, there are no performance concerns, as the scaling factor (big O) is the same. Each node will still only be visited once.

The order in which elements are yielded remains unchanged, but each will now be yielded with its ancestor stack attached. That means that for our example tree, each element will be replaced by the following:

• 0 -> [0],
• 1 -> [0, 1],
• 2 -> [0, 2],
• 3 -> [0, 1, 3],
• 4 -> [0, 1, 4],
• 5 -> [0, 2, 5],
• 6 -> [0, 2, 6],
• 7 -> [0, 2, 6, 7],
• 8 -> [0, 2, 6, 7, 8],
• 9 -> [0, 2, 6, 7, 8, 9],
• 10 -> [0, 2, 6, 7, 8, 9, 10]

Example Tree:
       0
      / \
     1   2
    / \ / \
   3  4 5  6
          /
         7
          \
           8
          /
         9
          \
          10

More technical details:

Because this operation transforms the iterator into a StreamingIterator, the slices cannot be saved and used across loop iterations, as the slice points to internal iterator memory and is altered with the .next() call. Each slice must be collected into a Vec or other data structure by the caller to save them for later. This operation will incur a performance penalty and this library does not assume you want that performance penalty by default.

Since this iterator is no longer a Rust Iterator, for loops will no longer work. See details on how to work around this in the streaming-iterator crate.

// Example usage:
use streaming_iterator::StreamingIterator;
use tree_iterators_rs::{
    prelude::*,
    examples::create_example_binary_tree
};

let root = create_example_binary_tree();
let mut result = String::new();

// any iterator method can be swapped in here
root.dfs_preorder()
    .attach_ancestors()
    .filter(|slice|
        slice.iter().all(|value| *value % 2 == 0)
    )
    .map(|slice| slice[slice.len() - 1])
    .for_each(|value| {
        result.push(' ');
        result.push_str(&value.to_string())
    });

println!("{}", result);

Object Safety

This trait is not object safe.

Implementors