I write for engineers. I write about web technology, coding patterns, and best practices from my learnings.
left
child and right
child. We can translate the description into Rust code like this:pub struct BinaryTree<T> {
pub value: T,
pub left: Option<Box<BinaryTree<T>>>,
pub right: Option<Box<BinaryTree<T>>>,
}
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.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 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.Box
is one of the smart pointers. It saves an address that points to data in memory. Box
helps us to create a BinaryTree
struct with an unknown size so that we can grow the Binary Tree by inserting nodes without thinking ahead how many nodes we'll have when creating the tree.impl<T> BinaryTree<T> {
pub fn new(value: T) -> Self {
BinaryTree {
value,
left: None,
right: None,
}
}
}
new
T
and return a BinaryTree
that holds the value and no child nodes.BinaryTree::new
to create a root node, we can think about how to insert child nodes. Intuitively, it would be great if we could insert the left or right child node by calling methods on the root node instance. Like this:BinaryTree::new(1)
.left(BinaryTree::new(2))
.right(BinaryTree::new(3))
impl<T> BinaryTree<T> {
pub fn new(value: T) -> Self {
BinaryTree {
value,
left: None,
right: None,
}
}
pub fn left(mut self, node: BinaryTree<T>) -> Self {
self.left = Some(Box::new(node));
self
}
pub fn right(mut self, node: BinaryTree<T>) -> Self {
self.right = Some(Box::new(node));
self
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn create_new_tree() {
let tree = BinaryTree::new(1);
assert_eq!(tree.value, 1);
}
#[test]
fn insert_left() {
let tree = BinaryTree::new(1).left(BinaryTree::new(2));
if let Some(node) = tree.left {
assert_eq!(node.value, 2);
}
assert_eq!(tree.right, None);
}
#[test]
fn insert_right() {
let tree = BinaryTree::new(1).right(BinaryTree::new(2));
if let Some(node) = tree.right {
assert_eq!(node.value, 2);
}
assert_eq!(tree.left, None);
}
}
BinaryTree::new(1)
.left(
BinaryTree::new(2)
.left(BinaryTree::new(4))
.right(BinaryTree::new(5))
)
.right(BinaryTree::new(3))
If I just want to create abalanced Binary Tree without any other requirements, can I insert a node and the tree finds the next available spot for me?
let mut root = BinaryTree::new(1);
root.insert(2);
root.insert(3);
root.insert(4);
root.insert(5);
VecDequeue
in the standard library we can use.pub fn insert(&mut self, new_value: T) {
let mut queue: VecDeque<&mut BinaryTree<T>> = VecDeque::new();
queue.push_front(self);
loop {
let BinaryTree {
ref mut left,
ref mut right,
..
} = queue.pop_back().unwrap();
match left {
Some(node) => {
queue.push_front(node);
}
None => {
*left = Some(Box::new(BinaryTree::new(new_value)));
return;
}
}
match right {
Some(node) => {
queue.push_front(node);
}
None => {
*right = Some(Box::new(BinaryTree::new(new_value)));
return;
}
}
}
}
left
or right
child is absent. If we find one, that's the next available spot for the new node.insert
method together.self
. self
is referring to the BinaryTree
instance the method is called on. What we need from self
is to be able to mutate the left
and right
child node so that we can insert a new node. Simply passing in a mutable reference &mut self
will do the job because the method doesn't need to take ownership of self
.VecDeque
item data type, we can use the same data type as self
to store mutable references of BinaryTree
.left
and right
because we want to insert the new node.left
and right
to allow the new node assignment, like this: *left = Some(Box::new(BinaryTree::new(new_value)))
.#[test]
fn insert() {
let mut tree = BinaryTree::new(1);
tree.insert(2);
tree.insert(3);
tree.insert(4);
tree.insert(5);
assert_eq!(
tree,
BinaryTree::new(1)
.left(
BinaryTree::new(2)
.left(BinaryTree::new(4))
.right(BinaryTree::new(5))
)
.right(BinaryTree::new(3))
);
tree.insert(6);
assert_eq!(
tree,
BinaryTree::new(1)
.left(
BinaryTree::new(2)
.left(BinaryTree::new(4))
.right(BinaryTree::new(5))
)
.right(BinaryTree::new(3).left(BinaryTree::new(6)))
)
}
PartialEq
trait to the BinaryTree
struct.+ #[derive(PartialEq)]
pub struct BinaryTree<T> {
pub value: T,
pub left: Option<Box<BinaryTree<T>>>,
pub right: Option<Box<BinaryTree<T>>>,
}
insert
method, we can consider creating a balanced tree more conveniently. For example, I want to have something similar to Vec::from
: an associated function BinaryTree::from
that takes in an array and returns a balanced BinaryTree
.#[test]
fn create_new_tree_with_from() {
// `BinaryTree::from` takes in a reference of an array because borrowing is sufficient
let tree = BinaryTree::from(&[1, 2, 3, 4, 5, 6]);
assert_eq!(
tree,
BinaryTree::new(1)
.left(
BinaryTree::new(2)
.left(BinaryTree::new(4))
.right(BinaryTree::new(5))
)
.right(BinaryTree::new(3).left(BinaryTree::new(6)))
)
}
BinaryTree::from
, we can iterate through the array and use the insert
method to create the tree structure.impl<T> BinaryTree<T> {
pub fn from(new_values: &[T]) -> Self {
let (first, rest) = new_values.split_first().unwrap();
let mut root: BinaryTree<T> = BinaryTree::new(*first);
for value in rest {
root.insert(*value)
}
root
}
}
T
implements the Copy
trait.- impl<T> BinaryTree<T> {
+ impl<T> BinaryTree<T>
+ where
+ T: Copy,
+ {
insert
method actually take ownership over new_value
. In order to keep the program memory saved, the compiler didn't allow us to "move" the array elements into the insert
method because the array might be referenced in other parts of the program. So what we can do is to pass in a copy (duplicate) of an array element.#[derive(Debug, PartialEq)]
pub struct BinaryTree<T> {
pub value: T,
pub left: Option<Box<BinaryTree<T>>>,
pub right: Option<Box<BinaryTree<T>>>,
}
impl<T> BinaryTree<T>
where
T: Copy,
{
///
/// Create a new Binary Tree node.
///
pub fn new(value: T) -> Self {
BinaryTree {
value,
left: None,
right: None,
}
}
///
/// Create a balanced tree from an array reference.
///
pub fn from(new_values: &[T]) -> Self {
let (first, rest) = new_values.split_first().unwrap();
let mut root: BinaryTree<T> = BinaryTree::new(*first);
for value in rest {
root.insert(*value)
}
root
}
///
/// Insert a tree node in the next available branch with breadth first traversal.
///
pub fn insert(&mut self, new_value: T) {
let mut queue: VecDeque<&mut BinaryTree<T>> = VecDeque::new();
queue.push_front(self);
loop {
let BinaryTree {
ref mut left,
ref mut right,
..
} = queue.pop_back().unwrap();
match left {
Some(node) => {
queue.push_front(node);
}
None => {
*left = Some(Box::new(BinaryTree::new(new_value)));
return;
}
}
match right {
Some(node) => {
queue.push_front(node);
}
None => {
*right = Some(Box::new(BinaryTree::new(new_value)));
return;
}
}
}
}
///
/// Insert a left child node.
///
pub fn left(mut self, node: BinaryTree<T>) -> Self {
self.left = Some(Box::new(node));
self
}
///
/// Insert a right child node.
///
pub fn right(mut self, node: BinaryTree<T>) -> Self {
self.right = Some(Box::new(node));
self
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn create_new_tree() {
let tree = BinaryTree::new(1);
assert_eq!(tree.value, 1);
}
#[test]
fn insert_left() {
let tree = BinaryTree::new(1).left(BinaryTree::new(2));
if let Some(node) = tree.left {
assert_eq!(node.value, 2);
}
assert_eq!(tree.right, None);
}
#[test]
fn insert_right() {
let tree = BinaryTree::new(1).right(BinaryTree::new(2));
if let Some(node) = tree.right {
assert_eq!(node.value, 2);
}
assert_eq!(tree.left, None);
}
#[test]
fn insert() {
let mut tree = BinaryTree::new(1);
tree.insert(2);
tree.insert(3);
tree.insert(4);
tree.insert(5);
assert_eq!(
tree,
BinaryTree::new(1)
.left(
BinaryTree::new(2)
.left(BinaryTree::new(4))
.right(BinaryTree::new(5))
)
.right(BinaryTree::new(3))
);
tree.insert(6);
assert_eq!(
tree,
BinaryTree::new(1)
.left(
BinaryTree::new(2)
.left(BinaryTree::new(4))
.right(BinaryTree::new(5))
)
.right(BinaryTree::new(3).left(BinaryTree::new(6)))
)
}
#[test]
fn create_new_tree_from() {
let tree = BinaryTree::from(&[1, 2, 3, 4, 5, 6]);
assert_eq!(
tree,
BinaryTree::new(1)
.left(
BinaryTree::new(2)
.left(BinaryTree::new(4))
.right(BinaryTree::new(5))
)
.right(BinaryTree::new(3).left(BinaryTree::new(6)))
)
}
}
Option
TypeBox
PointerVecDequeue
PartialEq
TraitCopy
TraitVec::from
null