Skip to content

Instantly share code, notes, and snippets.

@shivshank
Created November 14, 2017 01:34
Show Gist options
  • Save shivshank/40d4362b36013263af041f9c5cdcd8ee to your computer and use it in GitHub Desktop.
Save shivshank/40d4362b36013263af041f9c5cdcd8ee to your computer and use it in GitHub Desktop.
Fixed Depth Binary Tree
use std::fmt::Debug;
trait BtreeTrait: Debug {}
#[derive(Debug)]
struct Btree<T: Debug, Tail: BtreeTrait> {
val: T,
left: Option<Tail>,
right: Option<Tail>,
}
impl<T: Debug, Tail: BtreeTrait> Btree<T, Tail> {
fn leaf(val: T) -> Btree<T, Tail> {
Btree { val, left: None, right: None}
}
fn go_left(&self) -> Result<&Tail, ()> {
self.left.as_ref().ok_or(())
}
fn go_right(&self) -> Result<&Tail, ()> {
self.right.as_ref().ok_or(())
}
}
impl<T: Debug, Tail: BtreeTrait> BtreeTrait for Btree<T, Tail> {}
#[derive(Debug)]
struct BtreeTail;
impl BtreeTrait for BtreeTail {}
type ThreeLevelBtree<T> = Btree<T, Btree<T, Btree<T, BtreeTail>>>;
fn main() {
let mut tree: ThreeLevelBtree<i32> = Btree::leaf(10);
tree.left = Some(Btree::leaf(3));
// delete it!
tree.left = None;
tree.right = Some(Btree::leaf(-5));
// With more elbow grease I think you could pull off
// assert_eq!(tree.go_left().go_right(), Err(()));
// where go_X returns a Result whose error type says either no value present
// or the entire branch ended earlier in the chain; the Ok value is `val`
tree.right
.as_mut()
.unwrap()
.left = Some(Btree::leaf(-3));
println!("{:?}", tree);
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment