Tree data structures in Rust with tree-ds (#1: Getting Started)

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 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:

[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.

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.

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.

[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:

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.

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));

print("{}", 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.