If you enjoy using this crate, please star the github repo so I as the author can feel good about releasing it as open source.
treeiteratorsrs is a library built to provide you with the utilities/iterators to easily work with tree data structures in Rust. It provides a default implementation for the majority use cases. These include:
1. TreeNode
This crate is written such that you can build your own implementations as well using other collection types.
This crate uses no unsafe code!
The largest benefit of using this library other than the amount of complexity it can effectively abstract away is that the various tree iterators are interchangeable in the for/while loop syntax. This means you can write your code to use a breadth-first-search today and trivially swap it out for a depth-first pre or postorder search tomorrow without significantly changing the structure of your code. Syntactically, this library is also able to hide a lot of complexity and provide a friendly interface.
The other benefit of this library is its tight integration with the rest of Rust's iterators. Because each API returns an iterator, you can proceed to use the iterator APIs like filter, map, and reduce on your trees which can very powerfully simplify code.
The easiest way to get started is to simply add this crate as a dependency and add a using statement to pull in its prelude (treeiteratorsrs::prelude::*). You can then create your data structure using the BinaryTreeNode or TreeNode structs provided and build on top of it. These structs provide default implementations of all functionality in this crate. The methods that come attached to these structs include the following (all of which have open source code that can be found in this file): - Owned Iterator APIs - these take ownership of the TreeNode similarly to an intoiter() call. - bfs() - dfspreorder() - dfspostorder() - dfsinorder() - this iterator is only available on BinaryTreeNode - Mutable borrow APIs - these do not take ownership and behave similarly to an itermut() call. - bfsitermut() - dfspreorderitermut() - dfspostorderitermut() - dfsinorderitermut - this iterator is only available on BinaryTreeNode - Borrow APIs - these do not take ownership and behave similarly to an iter() call. - bfsiter() - dfspreorderiter() - dfspostorderiter() - dfsinorderiter() - this iterator is only available on BinaryTreeNode - In addition, all of these APIs have an additional method (attachancestors()) that can be chained. This method changes the iterator to return a slice of references to the current tree value, as well as all of its parent values. For more details, see Examples.
For all of the following examples, we will use the tree structure as follows. It is complicated enough to convey the tree iterators' behavior thoroughly without being overwhelming. Code to build this tree using both the BinaryTreeNode and TreeNode structs is provided below.
mermaid
flowchart TD
A[0] --> B{1}
A --> C{2}
B --> D{3}
B --> E{4}
D --> Z{None}
D --> Y{None}
E --> X{None}
E --> W{None}
C --> F{5}
F --> V{None}
F --> U{None}
C --> G{6}
G --> H{7}
G --> T{None}
H --> S{None}
H --> I{8}
I --> J{9}
I --> R{None}
J --> Q{None}
J --> K{10}
K --> P{None}
K --> O{None}
Using BinaryTreeNode
```rust
use treeiteratorsrs::prelude::*;
fn createexamplebinarytree() -> BinaryTreeNode
Using TreeNode
rust
use tree
fn createexampletree() -> TreeNode
All 3 APIs' usages are identical other than their borrowing model, so only one example will be given. Say we want to join all of the values in our test tree into a string. We can do this as follows: ```rust // Tree creation (see above documentation) let root = createexampletree();
let mut result = String::new(); for value in root.bfs() { result.pushstr(&value.tostring()); result.push_str(", "); }
// result: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, println!("{}", result); ```
This code could also be written using Rust's iterator APIs: ```rust // Tree creation (see above documentation) let root = createexampletree();
let result =
root.bfs()
.map(|val| val.to_string())
.collect::
// result: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, println!("{}", result); ```
An equivalent set of code not using this crate would look like this: ```rust // Tree creation (see above documentation) let root = createexampletree();
let mut result = String::new();
let mut queue = VecDeque::new(); queue.pushback(root); while queue.len() > 0 { if let Some(front) = queue.popfront() { if let Some(children) = front.children { for child in children { queue.push_back(child); } }
result.push_str(&front.value.to_string());
result.push_str(", ");
}
}
// result: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, println!("{}", result); ```
Similarly to the BFS example, all 3 APIs' usages are identical other than their borrowing model, so only one example will be given. Say we want to join all of the values in our test tree into a string. We can do this as follows:
```rust // Tree creation (see above documentation) let root = createexampletree();
let mut result = String::new(); for value in root.dfspreorder() { result.pushstr(&value.tostring()); result.pushstr(", "); }
// result: 0, 1, 3, 4, 2, 5, 6, 7, 8, 9, 10, println!("{}", result); ```
This code could also be written using Rust's iterator APIs: ```rust // Tree creation (see above documentation) let root = createexampletree();
let result =
root.dfspreorder()
.map(|val| val.tostring())
.collect::
// result: 0, 1, 3, 4, 2, 5, 6, 7, 8, 9, 10, println!("{}", result); ```
An equivalent set of code not using this crate would look like this: ```rust // Tree creation (see above documentation) let root = createexampletree();
let mut result = String::new();
let mut stack = vec![root]; while stack.len() > 0 { if let Some(top) = stack.pop() { if let Some(mut children) = top.children { children.reverse(); for child in children { stack.push(child); } }
result.push_str(&top.value.to_string());
result.push_str(", ");
}
}
// result: 0, 1, 3, 4, 2, 5, 6, 7, 8, 9, 10, println!("{}", result); ```
Similarly to the other examples, all 3 APIs' usages are identical other than their borrowing model, so only one example will be given. Say we want to join all of the values in our test tree into a string. We can do this as follows: ```rust // Tree creation (see above documentation) let root = createexamplebinary_tree();
let mut result = String::new(); for value in root.dfsinorder() { result.pushstr(&value.tostring()); result.pushstr(", "); }
// result: 3, 1, 4, 0, 5, 2, 7, 9, 10, 8, 6,
println!("{}", result);
This code could also be written using Rust's iterator APIs:
rust
// Tree creation (see above documentation)
let root = createexamplebinary_tree();
let mut result = root.dfspreorder()
.map(|val| val.tostring())
.collect::
// result: 3, 1, 4, 0, 5, 2, 7, 9, 10, 8, 6,
println!("{}", result);
An equivalent set of code not using this crate would look like the following. It is important to note that the dfs_inorder API does not use recursion and thus does not incur the overhead of stack frames that this example does. For purposes of simplicity in the example, recursion was chosen. Rust's ownership model is difficult to work around with this traversal type and would make the example more complex than necessary.
rust
fn dfsinorder(node: Option
}
// Tree creation (see above documentation) let root = createexamplebinary_tree();
let mut result = String::new(); dfs_inorder(Some(Box::new(root)), &mut result);
// result: 3, 1, 4, 0, 5, 2, 7, 9, 10, 8, 6, println!("{}", result); ```
Similarly to the BFS and other DFS examples, all 3 APIs' usages are identical other than their borrowing model, so only one example will be given. Say we want to join all of the values in our test tree into a string. We can do this as follows: ```rust // Tree creation (see above documentation) let root = createexampletree();
let mut result = String::new(); for value in root.dfspostorder() { result.pushstr(&value.tostring()); result.pushstr(", "); }
// result: 3, 4, 1, 5, 10, 9, 8, 7, 6, 2, 0,
println!("{}", result);
This code could also be written using Rust's iterator APIs:
rust
// Tree creation (see above documentation)
let root = createexampletree();
let result =
root.dfspostorder()
.map(|val| val.tostring())
.collect::
// result: 3, 4, 1, 5, 10, 9, 8, 7, 6, 2, 0, println!("{}", result); ```
An equivalent set of code not using this crate would look like the following. It is important to note that the dfspostorder API does not use recursion and thus does not incur the overhead of stack frames that this example does. For purposes of simplicity in the example, recursion was chosen. Rust's ownership model is difficult to work around with this traversal type and would make the example more complex than necessary.
```rust
fn dfspostorder(node: TreeNode
result.push_str(", ");
result.push_str(&node.value.to_string());
}
// Tree creation (see above documentation) let root = createexampletree();
let mut result = String::new(); dfs_postorder(root, &mut result);
// result: 3, 4, 1, 5, 10, 9, 8, 7, 6, 2, 0, println!("{}", result); ```
attach_ancestors() is a method that can be called after any of the above APIs to change the iterator structure into one that returns a slice of all ancestors and the current value in the tree. If one of these is called, the (now streaming) iterator will yield a slice where the item at index 0 is the root value, the item at index len() - 1 is the current value, and everything in between is the other ancestors. As an example, when we are at the value of 10 in our traversal (see above documentation), the slice will look like this: [0, 2, 6, 7, 8, 9, 10].
For example, we can use this API to filter down to only the values where all of the ancestors and the current node are even numbers in the example tree.
NOTE: Be sure to add a use statement for streamingiterator::StreamingIterator to pull in the filter, map, reduce, foreach, etc. methods from the streaming_iterator crate.
```rust use streaming_iterator::StreamingIterator;
let root = createexampletree(); let mut result = String::new();
root.dfspreorderiter() .attachancestors() .filter(|slice| slice.iter().all(|value| **value % 2 == 0) ) .map(|slice| slice[slice.len() - 1]) .foreach(|value| { result.push(' '); result.pushstr(&value.tostring()) });
// result: 0 2 6 println!("{}", result); ```
We can do the same with the in order iterator if we use a binary tree:
```rust use streaming_iterator::StreamingIterator;
let root = createexamplebinary_tree(); let mut result = String::new();
root.dfsinorderiter() .attachancestors() .filter(|slice| slice.iter().all(|value| **value % 2 == 0) ) .map(|slice| slice[slice.len() - 1]) .foreach(|value| { result.push(' '); result.pushstr(&value.tostring()) });
// result: 0 2 6 println!("{}", result); ```
We can do the same with the postorder iterator to get the result in reverse:
```rust use streaming_iterator::StreamingIterator;
let root = createexampletree(); let mut result = String::new();
root.dfspostorderiter() .attachancestors() .filter(|slice| slice.iter().all(|value| **value % 2 == 0) ) .map(|slice| slice[slice.len() - 1]) .foreach(|value| { result.push(' '); result.pushstr(&value.tostring()) });
// result: 6 2 0 println!("{}", result); ```
And we can do the same with a breadth-first search. This just so happens to yield the same result as the depth first preorder iterator:
```rust use streaming_iterator::StreamingIterator;
let root = createexampletree(); let mut result = String::new();
root.bfsiter() .attachancestors() .filter(|slice| slice.iter().all(|value| **value % 2 == 0) ) .map(|slice| slice[slice.len() - 1]) .foreach(|value| { result.push(' '); result.pushstr(&value.to_string()) });
// result: 0 2 6 println!("{}", result); ```
This crates' APIs are powered by 3 traits. The traits include: 1. OwnedTreeNode/OwnedBinaryTreeNode - these traits powers the bfs(), dfspreorder(), dfsinorder() and dfspostorder() APIs. 2. MutBorrowedTreeNode/MutBorrowedBinaryTreeNode - these traits powers the bfsitermut(), dfspreorderitermut(), dfsinorderitermut and dfspostorder() APIs. 3. BorrowedTreeNode/BorrowedBinaryTreeNode - these traits powers the bfsiter(), dfspreorderiter(), dfsinorderiter() and dfspostorder_iter() APIs.
You may pick and choose which of the traits you implement to suit your needs. They are identical apart from some naming conventions and the ownership of the value returned from their required method implementation.
As an example, we can implement another TreeNode variant that uses a Linked List to hold its children. All code here is MIT licensed and you are free to directly copy or modify it as you see fit subject to the conditions of the license. ```rust use crate::prelude::*; use std::collections::LinkedList;
struct LLTreeNode
This is a good start, but realistically we want it to implement all of the tree traversal APIs available to us.
We can start with the OwnedTreeNode implementation as follows. Since we chose to use a LinkedList as our children property, we have to wrap its iterator in a Some() Option variant. The hardest part of implementing this is figuring out the type of LinkedList's intoiter() method return type. ```rust use std::collections::linkedlist::IntoIter;
impl
fn get_value_and_children(self) -> (Self::OwnedValue, Option<Self::OwnedChildren>) {
(
self.value,
Some(self.children.into_iter())
)
}
} ``` Now that we have implemented OwnedTreeNode, our type has the bfs(), dfspreorder(), and dfspostorder() methods.
The mutable borrow implementation is very similar to the owned one. The only difference is that the 'Value' associated type changed to a mutable reference and we are calling itermut() instead of intoiter(). ```rust use std::collections::linked_list::IterMut;
impl<'a, T> MutBorrowedTreeNode<'a> for LLTreeNode
type MutBorrowedValue = &'a mut T;
type MutBorrowedChildren = IterMut<'a, LLTreeNode<T>>;
fn get_value_and_children_iter_mut(&'a mut self) -> (Self::MutBorrowedValue, Option<Self::MutBorrowedChildren>) {
(
&mut self.value,
Some(self.children.iter_mut())
)
}
} ``` Now that we have implemented MutBorrowedTreeNode, our type has the bfsitermut(), dfspreorderitermut(), and dfspostorderitermut() methods.
The borrow implementation is also very similar to the owned one. The only difference is that the 'Value' associated type changed to an immutable reference and we are calling iter() instead of intoiter(). ```rust use std::collections::linkedlist::Iter;
impl<'a, T> BorrowedTreeNode<'a> for LLTreeNode
type BorrowedValue = &'a T;
type BorrowedChildren = Iter<'a, LLTreeNode<T>>;
fn get_value_and_children_iter(&'a self) -> (Self::BorrowedValue, Option<Self::BorrowedChildren>) {
(
&self.value,
Some(self.children.iter())
)
}
} ``` Now that we have implemented BorrowedTreeNode, our type has the bfsiter(), dfspreorderiter(), and dfspostorder_iter() methods.
This library is purposely very loose in its trait declarations, so it opens the door to some pretty exotic data transformations and use cases. Each iterator is as lazy as possible and only calls the getvalueand_children method variant once per node in the tree. This means you are able to lazily build/generate the tree as traversal progresses if you choose to. This opens the door to using this library to do some crazy things. I would love to hear about any use cases like this that you come up with. Please leave a note/issue on the github repo!