Binary Search Tree in Rust

bst.rs

struct BST<K: Ord + Clone, V: Ord + Clone> {
    key: Option<K>,
    value: Option<V>,
    left: Option<Box<BST<K, V>>>,
    right: Option<Box<BST<K, V>>>,
}

impl<K: Ord + Clone, V: Ord + Clone> BST<K, V> {
    fn init() -> Box<BST<K, V>> {
        return Box::new(BST::<K, V> {
            key: None,
            value: None,
            left: None,
            right: None,
        });
    }

    fn insert_option(o: Option<Box<BST<K, V>>>, key: K, value: V) -> Option<Box<BST<K, V>>> {
        let mut bst = if let Some(bst) = o {
            bst
        } else {
            BST::<K, V>::init()
        };

        bst.insert(key, value);
        return Some(bst);
    }

    fn insert(&mut self, key: K, value: V) {
        let thiskey = if let Some(thiskey) = &self.key {
            thiskey
        } else {
            self.key = Some(key);
            self.value = Some(value);
            return;
        };

        if key < *thiskey {
            self.left = BST::insert_option(self.left.take(), key, value);
            return;
        }

        self.right = BST::insert_option(self.right.take(), key, value);
    }

    fn lookup(&self, key: K) -> Option<V> {
        let (thiskey, thisvalue) =
            if let (Some(thiskey), Some(thisvalue)) = (&self.key, &self.value) {
                (thiskey, thisvalue)
            } else {
                return None;
            };

        if key == *thiskey {
            return Some(thisvalue.clone());
        }

        if key < *thiskey {
            if let Some(l) = &self.left {
                return l.lookup(key);
            }
        }

        if let Some(r) = &self.right {
            return r.lookup(key);
        }

        return None;
    }
}

fn debug_lookup(b: Box<BST<String, String>>, key: String) {
    let val = b.lookup(String::from("x"));
    if let Some(val) = val {
        println!("{}: {}", key, val);
    } else {
        println!("{}: Not found", key);
    }
}

fn main() {
    let mut b = BST::<String, String>::init();
    b.insert(String::from("y"), String::from("200"));
    b.insert(String::from("x"), String::from("100"));

    debug_lookup(b, String::from("x"));
}

console

$ rustc bst.rs
$ ./bst
x: 100

Hi, is it safe to assume that the insert_option method is a helper one, and not part of the "formal" BST api? I am looking for ways to play around with this gist and refactor it a little bit.

Awesome! Yup, insert_option is "private".