Tree data structures in Rust with tree-ds (#1: Getting Started)
Tags: rust, algorithms, datastructures, tree
Published: 2024-06-22 05:54:34

Trees are a fundamental data structure used across various applications. In Rust, building your own tree from scratch can be a great learning experience, but for production use, consider leveraging existing crates. In this three part series, we'll explore the `tree-ds` crate, a powerful tool for working with trees in your Rust projects.

## Introducing `tree-ds`

The [`tree-ds`](https://github.com/clementwanjau/tree-ds) crate, provides a versatile tree implementation in Rust. It offers a generic Tree struct that can hold any data type as its node value. The crate also supports various tree operations, making it a comprehensive solution for your tree-based needs.

## Getting Started

To use `tree-ds`, add the following line to your `Cargo.toml` dependencies:
```toml
[dependencies]
tree-ds = "0.1"
```

Once you've added the dependency, you can start using the Tree struct in your code. The tree struct is defined as a generic type, `Tree<Q, T>`, where `Q` is the type of the node id and `T` is the type of the node value. Depending on your use case, you may want different types for the node Id. Optionally, trees can also be named by passing in the name when creating a new tree. 
```rust
use tree_ds::prelude::*;

let mut tree = Tree::new(Some("Tree name"));
```

Nodes build up the tree. The `Node` type is a generic struct that can hold any arbitrary type of data for versatility. It is declared as `Node<Q, T>`. The `Q` and `T` types are passed from the tree type. You create a node by providing the node id and the optional value.
```rust
let node = Node::new("CEO", Some("John Doe"));
```
In some complex cases, manually specifying the id of every node becomes unfeasible especially since every node in the tree must have a unique id. In such cases, the `auto_id` feature flag saves the day.
In the `Cargo.toml` file, enable the `auto_id` feature.
```toml
[dependencies]
tree-ds = { version = "0.1", features = ["auto_id"] }
```
To create a node with an auto generated id, you use the `new_with_auto_id` method:

```rust
let node = Node::new_with_auto_id(Some("Node Value"));
```

You then add nodes to the tree using the `add_node` method of the tree specifying the node to add and the optional id of the parent node. This method returns the id of the added node which makes it convenient to use.
 
```rust
use tree_ds::prelude::*;

let mut tree = Tree::new(Some("Corporate Structure"));
// This is the root node so we pass None to the parent_id arg.
let ceo_node = tree.add_node(Node::new("CEO", Some("John Doe")), None)?;
let cto_node = tree.add_node(Node::new("CTO", Some("Jane Doe")), Some(&ceo_node))?;
let cfo_node = tree.add_node(Node::new("CFO", Some("James Doe")), Some(&ceo_node))?;

println!("{}", tree);
```

This code snippet creates a new Tree with the name `"Corporate Structure"`. We then insert three nodes, `"ceo_node"` as the root node, `"cto_node"` and `"cfo_node"` as children of the root node. Finally, we print the value of the tree.

Adding multiple root nodes results in an error.

## Conclusion
In this section we went through getting started with the `tree-ds` crate, creating trees and nodes and adding nodes to the tree. In the next section we will explore the various operations you can perform on the tree.

[Read The Next Post](https://dev.to/clementwanjau/tree-data-structures-in-rust-with-tree-ds-2-tree-operations-54ph)