Roast my dumb BinaryTree implementation
Hi guys,
I'm a rust newbie. After finishing rustaceans I decided to try implementing a binary tree.
I struggled a lot trying to get the borrows right, and compiler screamed a lot at me especially when I tried to hold multiple mutable references (forgot they are exclusive). I managed to get it compiled but I'm not satisfied with the insert method as it looks kinda ugly and probably more complex than it should be, and I believe it's unidiomatic. I think a lot of that came from trying not to drop or move a Box, hence the \ref mut\\s. Could you mind giving me some guidance? What can i do to make this more idiomatic?
#[derive(Debug)]
pub struct Node<T> {
pub value: T,
pub left: Option<Box<Node<T>>>,
pub right: Option<Box<Node<T>>>,
}
impl<T> Node<T> {
fn new(value: T) -> Self {
Node{value: value, left: None, right: None}
}
}
#[derive(Debug)]
pub struct BinaryTree<T>
where T: PartialOrd {
pub root: Option<Box<Node<T>>>
}
impl<T: PartialOrd> BinaryTree<T> {
fn new() -> Self {
BinaryTree { root: Option::None }
}
fn is_empty(&self) -> bool {
return self.root.is_none();
}
fn insert(&mut self, value: T) {
if let Some(ref mut node) = self.root {
let mut node = node.as_mut();
loop {
if value < node.value {
if let Some(ref mut child) = node.left {
node = child.as_mut();
} else {
let new_node = Box::new(Node::new(value));
node.left = Some(new_node);
break;
}
} else if value > node.value {
if let Some(ref mut child) = node.right {
node = child.as_mut();
} else {
let new_node = Box::new(Node::new(value));
node.right = Some(new_node);
break;
}
} else {
break;
}
}
} else {
let new_node = Box::new(Node::new(value));
self.root = Some(new_node);
}
}
}
fn main() {
let mut my_tree = BinaryTree::<i32>::new();
my_tree.insert(5);
my_tree.insert(7);
my_tree.insert(3);
my_tree.insert(10);
println!("{:?}", my_tree);
}