# 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**

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

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

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

- 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.
- If you find an existing node in your insertion target, just repeat the
`insert()`

process for that node. - 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**

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!