A binary search tree in rust (trunk version, I guess 0.6).

gistfile1.rs

extern mod std;
use core::cmp::*;

fn main() {
  let mut b = BST::<int> { Root: @None };
	b.add(8);
	b.add(3);
	b.add(6);
	b.add(7);
	b.add(4);
	b.add(1);
	b.add(10);
	b.add(14);
	b.add(13);
	let f = 100;
	let in = b.contains(f);
	io::println(fmt!("%?", b));
	io::println(fmt!("%d? %?", f, in));
}

enum Maybe<T> {
	None,
	Some(@mut Node<T>)
}

struct Node<T> {
	Data: T,
	Left: @Maybe<T>,
	Right: @Maybe<T>
}

struct BST<T> {
	Root: @Maybe<T>
}

fn BST_add<T: Ord + Eq>(t: &mut BST<T>, d: T) {
	match *t.Root {
		None => t.Root = make_node(d),
		Some(r) => node_add(r, d)
	};
}

fn node_add<T: Ord + Eq>(n: &mut Node<T>, d: T) {
	if d < n.Data {
		match *n.Left {
			None => n.Left = make_node(d),
			Some(s) => node_add(s, d)
		};
	}
	else {
		match *n.Right {
			None => n.Right = make_node(d),
			Some(s) => node_add(s, d)
		};
	}
}

fn BST_contains<T: Ord + Eq>(t: &BST<T>, i: T) -> bool {
	match *t.Root {
		None => false,
		Some(n) => node_contains(n, i)
	}
}

fn node_contains<T: Ord + Eq>(n: &Node<T>, i: T) -> bool {
	if n.Data == i {
		true
	}
	else if n.Data < i {
		match *n.Right {
			None => false,
			Some(s) => node_contains(s, i)
		}
	}
	else {
		match *n.Left {
			None => false,
			Some(s) => node_contains(s, i)
		}
	}
}

fn make_node<T: Ord + Eq>(i: T) -> @Maybe<T> {
	@Some(@mut Node{Data: i, Left: @None, Right: @None})
}

impl<T: Ord + Eq> BST<T> {
	fn add(&mut self, i: T) {
		BST_add(self, i);
	}

	fn contains(&self, i: T) -> bool {
		BST_contains(self, i)
	}
}