Skip to content

Instantly share code, notes, and snippets.

@ymotongpoo
Created December 19, 2010 12:31
Show Gist options
  • Save ymotongpoo/747301 to your computer and use it in GitHub Desktop.
Save ymotongpoo/747301 to your computer and use it in GitHub Desktop.
test implementation of binary tree
type 'a tree = Lf | Bt of 'a * 'a tree * 'a tree
let rec size = function
| Lf -> 0
| Bt (_, l, r) -> 1 + (size l) + (size r)
let rec depth = function
| Lf -> 0
| Bt (_, l, r) -> 1 + max (depth l) (depth r)
let rec mem e = function
| Lf -> false
| Bt (x, l, r) -> x = e || mem e l || mem e r
let rec count e bt =
match bt with
| Lf -> 0
| Bt (x, l, r) ->
if x = e then 1 + count e l + count e r
else count e l + count e r
let rec map f = function
| Lf -> Lf
| Bt (x, l, r) -> Bt (f x, map f l, map f r)
let rec insert e bt =
match bt with
| Lf -> Bt (e, Lf, Lf)
| Bt (x, l, r) ->
match l, r with
| Lf, _ -> Bt (x, insert e l, r)
| _, Lf -> Bt (x, l, insert e r)
| _, _ -> Bt (x, insert e l, insert e r)
let rec update s bt t =
match bt with
| Lf -> Lf
| Bt (x, l, r) ->
if x = s
then Bt (t, update s l t, update s r t)
else Bt (x, update s l t, update s r t)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment