Implementation of binary search tree in OCaml and Rust (modeled after the OCaml solution).

README.md

Here's two implementations of a binary search tree in OCaml and Rust. The Rust version was written to deliberately look as close to the OCaml as possible (and it'd get pretty close if I used match instead of OCaml's variants). I'm pretty sure my OCaml implementation is idiomatic, and I'd like some advice on what steps I'd probably take to make the Rust example more idiomatic. My objective is to talk about how close the examples can be to each other as well as how different the examples can be (hopefully demonstrating strengths for both.)

Any other thoughts or ideas are also helpful and super appreciated!

tree.ml

type 'a tree =
    | Empty
    | Node of 'a * 'a tree * 'a tree
;;

let rec depth =  function
    | Empty -> 0
    | Node(_, left, right) -> 1 + max (depth left) (depth right)
;;

let rec insert x = function
    | Empty -> Node(x, Empty, Empty)
    | Node(value, left, right) ->
        if x < value then Node (value, insert x left, right)
        else Node (value, left, insert x right)
;;

let root = insert 5 Empty |> insert 4 |> insert 3 in
        print_string (string_of_int (depth root));;

tree.rs

#![feature(box_syntax, box_patterns)]

use std::cmp::max;

// Recursive structs must be referenced or be Box'd
enum Tree<T:PartialOrd> {
    Empty,
    Node(T,  Box<Tree<T>>,  Box<Tree<T>>)
}

fn depth<T:PartialOrd>(tree:Tree<T>) -> i32 {
    match tree {
        Tree::Empty => 0,
        Tree::Node(_, left, right) =>
            1 + max(depth(*left), depth(*right))
    }
}

fn insert<T: PartialOrd>(x: T, tree:Tree<T>) ->  Tree<T> {
    match tree {
        Tree::Empty =>
            Tree::Node(x, Box::new(Tree::Empty), Box::new(Tree::Empty)),
        Tree::Node(value, left, right) =>
            if x < value {
                Tree::Node(value, Box::new(insert(x, *left)), right)
            } else {
                Tree::Node(value, left, Box::new(insert(x, *right)))
            },
    }
}

fn main() {
    let tree = insert(2,
        insert(6,
            insert(3,
                insert(4,
                    insert(5, Tree::Empty)))));

    let num = depth(tree);
    print!("Depth is: {}", num);
}

I want people to leave feeling empowered to experiment and enthusiastic. Do you have any thoughts on that?

That sounds perfect :)