Binary Tree Insertion in Rust

Learning ownership in Rust with a classic data structure

TL;DR

• 🌳 We’ll implement a Binary Tree together.
• 🧑‍🌾 We’ll discuss a couple of ways to insert a node in a Binary Tree.
• 🧑‍🔬 We’ll discuss Rust’s ownership in action.
• ✨ We’ll touch on more features and syntax in Rust.

I was struggling hard with Rust’s ownership when implementing a Binary Tree so I pivoted and re-read about it. After taking my time understanding it and refactoring my code, I finally made a breakthrough😎 I’m very excited to share with you the awesome features in Rust I came across. You’ll see interesting concepts like smart pointers and ownership.

Let’s get it!

Data Structure

A Binary Tree data structure look like this:

Each node has no more than two child nodes. We refer them as left child and right child. We can translate the description into Rust code like this:

The BinaryTree struct holds a value with the generic type T. We use Option enum to represent that the left and right child are both optional.

A Option<T> is either a Some that contains a value of the type T, or a None that represents it doesn't. Because we are using Option to express whether a value is either something or nothing, the Rust compiler can check if we handle all the cases to prevent bugs.

Compared to JavaScript where we use null value to express the same concept, Option encourages me to handle use cases upfront and it saves me a lot of trouble in runtime.

The Box is one of the smart pointers. It saves an address that points to a data in memory. Boxhelps us to create a BinaryTree struct with an unknown size, so that we…