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!

rust-notes.md

1. The features are unused and should be removed. Otherwise can't use stable Rust.
2. I tend to avoid trait bounds on types (enum / struct) and only put them on the functions that really need it. Technically, depth doesn't need PartialEq, so I might split the impl block into different pieces.
3. Prefer where clauses for longer trait bounds. I just use them all the time; allowing ;
4. Spaces after :.
5. Accept &Tree for depth; there's no need to take ownership.
6. Return a usize instead of i32 (depth is conceptually limited by RAM) and there's no way it can be negative.
7. Use println! instead of print; you want newlines.

Optional

1. Instead of taking ownership of the tree to insert into it, accept a mutable reference. Otherwise, there are many deallocations / allocations.

Questions

Is is acceptable to insert the same value twice?

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

use std::cmp::max;

enum Tree<T>{
    Empty,
    Node(T, Box<Tree<T>>, Box<Tree<T>>)
}

impl<T> Tree<T>
    where T: PartialOrd
{
    fn depth(&self) -> usize {
        match *self {
            Tree::Empty => 0,
            Tree::Node(_, ref left, ref right) =>
                1 + max(left.depth(), right.depth())
        }
    }

    fn insert(self, value: T) -> Self {
        match self {
            Tree::Empty => {
                Tree::Node(value, Box::new(Tree::Empty), Box::new(Tree::Empty))
            },
            Tree::Node(old_value, left, right) => {
                if value < old_value {
                    Tree::Node(old_value, Box::new(left.insert(value)), right)
                } else {
                    Tree::Node(old_value, left, Box::new(right.insert(value)))
                }
            },
        }
    }

    fn insert_mut(&mut self, value: T) -> &mut Self {
        match *self {
            Tree::Empty => {
                *self = Tree::Node(value, Box::new(Tree::Empty), Box::new(Tree::Empty));
            },
            Tree::Node(ref old_value, ref mut left, ref mut right) => {
                if &value < old_value {
                    left.insert_mut(value);
                } else {
                    right.insert_mut(value);
                }
            }
        }

        self
    }
}

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

    println!("Depth is: {}", tree.depth());

    let mut tree = Tree::Empty;
    tree
        .insert_mut(5)
        .insert_mut(4)
        .insert_mut(3)
        .insert_mut(6)
        .insert_mut(2);

    println!("Depth is: {}", tree.depth());
}