Writing a Binary Search Tree in Rust

Introduction
Binary Search Trees are a convenient structure for storing data because search, access, insertion, and deletion operations have an average time complexity of O(log(n)) with a worst case of O(n). It‘s also useful for sorting because insertion into a BST is inherently sorted!

We’re covering trees in my DSA class this week and I happen to be learning Rust, so I thought I’d take the opportunity to explore the structure in my new favorite language!

The Template

Struct template for Binary Search Tree

Let’s walk through this step-by-step:

We’re first declaring a public struct BST whose fields can hold a generic type T. We want to limit T to types that implement primarily the Ord and Debug traits, optionally Copy; Ord allows ordinal value comparisons, Debug allows debug-formatted printing, and Copy is an optional trait that will allow us to unwrap Options for other special features (like GraphViz integration).

Each node in our BST can hold a value, a left node, and a right node. We’ll wrap the left and right children in pointers to other nodes, Box<BST<T>> , and wrap them again in an Option because a node doesn’t necessarily have a child. We can use this Option to ensure we cover all possible cases later on.

Instantiation

Instantiation functions for Binary Search Tree

When creating an instance of our BST, we might take two paths: a blank instance, for example creating an empty BST into which nodes can be inserted, or creating a node based on a value. new() and from() both create a new instance of our BST with these distinct purposes in mind.

Insertion

Insertion function for Binary Search Tree

Inserting things into a BST is where things might seem to get a little hairy, so let’s walk through the process.

1. Traverse the tree by comparing the new value to each node you reach. If the new value is less than (or equal to) the existing node’s value, set your target for insertion to the current node’s left child. If the new value is greater than the existing node’s value, set your target to the right.
2. If you find an existing node in your insertion target, just repeat the insert() process for that node.
3. If you find an empty space in your insertion target, create a node from() the new value and set your target space to be an Option on a Box to that node.

Minimum/Maximum

Ordered insertion gives us the ability to find the minimum and maximum values extremely easily! Again using recursion, we can just traverse the left/right children (less than/greater than respectively) until we can’t anymore. It’s like a gift for being responsible with our insertion!

Searching

Search function for Binary Search Tree

Recursive searching can also be a hairy thing to wrap your mind around, but Rust’s pattern matching goes a long way towards clearing things up! We start by making sure our current node has a value at all. If it doesn’t, we’ve reached the end of the line and can return false. If we find a value there, we can match again on a comparison between the target and the value in &self, here aliased as key. If this comparison comes out to Equal, we’ve found the element! The rest should feel familiar; if we’re looking for a value less than the current node, we just search() the left branch. Greater, search() right.

Conclusion
Binary search trees have some incredibly useful qualities that are only bolstered by Rust’s guarantees towards memory safety and efficiency. Its robust pattern matching also helps to make decision trees both exhaustive and more human-readable!