Tree data structures in Rust with tree-ds (#2: Tree Operations)

In the previous part, we explored how to get started with the tree-ds crate to work with tree data structures in rust. In this part, we are going to explore the various features and operations offered by the Tree struct.

Exploring the Features

tree-ds offers a variety of functionalities for working with your tree. Here are some key features:

• Node Insertion: Insert nodes as descendants of a particular node. This is achieved by the add_node method:

use tree_ds::prelude::*;

let mut tree = Tree::new(Some("Tree Name"));
tree.add_node(Node::new(1, Some(20_000)), None)?;

The above snippet creates a tree and adds a root node.

• Node(s) Removal: Remove nodes based on their node id. You can also specify how you want to handle the children of the node in question. If you decide to remove the node and its children, it is considered a pruning action. You can also decide to just remove the single node and attach the children to their grandparent.

use tree_ds::prelude::*;

let mut tree = Tree:new(Some("Tree name"));
let node_id = tree.add_node(Node::new(1, Some(20_000)), None)?;
tree.remove_node(&node_id, NodeRemovalStrategy::RemoveNodeAndChildren)?;

• Traversal: The crate provides methods for in-order, pre-order, and post-order tree traversals, allowing you to visit and process nodes in a specific order.

use tree_ds::prelude::{Node, Tree, TraversalStrategy};

let mut tree: Tree<i32, i32> = Tree::new(Some("Sample Tree"));
let node_1 = tree.add_node(Node::new(1, Some(2)), None)?;
let node_2 = tree.add_node(Node::new(2, Some(3)), Some(&node_1))?;
let node_3 = tree.add_node(Node::new(3, Some(6)), Some(&node_2))?;

let preordered_nodes = tree.traverse(TraversalStrategy::PreOrder, &node_1)?;

• Getting a whole subsection of a tree. A subsection is a list of nodes that are descendants to a node. Think of it as a branch with nodes.

use tree_ds::prelude::{Node, Tree}

let mut tree: Tree<i32, i32> = Tree::new(Some("Sample Tree"));

let node_1 = tree.add_node(Node::new(1, Some(2)), None)?;
let node_2 = tree.add_node(Node::new(2, Some(3)), Some(&node_1))?;
let node_3 = tree.add_node(Node::new(3, Some(6)), Some(&node_2))?;

let subsection = tree.get_subtree(&node_2, None)?;

• Grafting: Adding whole section of a tree or another tree onto a tree at a specified node.

use tree_ds::prelude::{Node, Tree, SubTree};

let mut tree: Tree<i32, i32> = Tree::new(Some("Sample Tree"));
let node_id = tree.add_node(Node::new(1, Some(2)), None)?;
let mut subtree = SubTree::new(Some("Sample Tree"));
let node_2 = subtree.add_node(Node::new(2, Some(3)), None)?;  subtree.add_node(Node::new(3, Some(6)), Some(&node_2))?;
tree.add_subtree(&node_id, subtree)?;

• Searching: Search for nodes based on their value and retrieve them if found.
• Enumerating the children and the ancestors of a node.
• Getting the height, degree and depth of a node.

These features, along with many more, make tree-ds a well-equipped solution for building and manipulating trees in your Rust projects.

Conclusion

In this section we went through some of the features of the tree data structure offered by the tree-ds crate. The crate is actively maintained so it is a good option to consider when working with trees in rust.

Read The Next Post