Skip to content

Instantly share code, notes, and snippets.

@kmicinski
Last active August 29, 2015 14:23
Show Gist options
  • Save kmicinski/d15e48213bc1359e646f to your computer and use it in GitHub Desktop.
Save kmicinski/d15e48213bc1359e646f to your computer and use it in GitHub Desktop.
OCaml tree insert
tree =
| Leaf of int option
| Node of int * tree * tree
let rec insert tree i = match tree with
| Leaf (None) -> Leaf (Some i)
| Leaf (Some y) ->
if (i = y) then tree
else (if (i < y) then
(*
insert (e.g.,) 10 into 20
20
10 ---> /
10
*)
Node(i,(Leaf (Some y)),Leaf None)
else
(*
insert (e.g.,) 20 into 10
20
20 ---> /
10
*)
Node(y,(Leaf (Some i)), Leaf (None)))
| Node (y,t1,t2) ->
if (i = y) then tree
else (if (i < y) then
(*
insert (e.g.,) 5 into
10
/ \
t1 t2
*)
Node(y,insert t1 i,t2)
else
(* Symmetric operation on right side *)
Node (y,t1,insert t2 i))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment