Fixed Depth Binary Tree

fd_btree.rs

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);
}