Binary Search Tree - Saga Examples

A simple binary search tree using an ADT and recursion.

The tree type

A tree is either empty or a node with a left subtree, a value, and a right subtree:

type Tree =
  | Empty
  | Node Tree Int Tree

Insert and lookup

Both functions recurse down the tree, branching left or right based on comparison:

insert t x = case t {
  Empty -> Node Empty x Empty
  Node l v r ->
    if x < v then Node (insert l x) v r
    else if x > v then Node l v (insert r x)
    else t
}

contains t x = case t {
  Empty -> False
  Node l v r ->
    if x == v then True
    else if x < v then contains l x
    else contains r x
}

In-order traversal

Walking the tree in order produces a sorted list:

to_list t = case t {
  Empty -> []
  Node l v r -> List.append (to_list l) (v :: to_list r)
}

Putting it together

main () = {
  let t = List.foldl insert Empty [5, 3, 7, 1, 4, 6, 8]

  to_list t |> dbg
  contains t 4 |> dbg
  contains t 9 |> dbg
}

Output:

[1, 3, 4, 5, 6, 7, 8]
True
False

Full source

type Tree =
  | Empty
  | Node Tree Int Tree

insert t x = case t {
  Empty -> Node Empty x Empty
  Node l v r ->
    if x < v then Node (insert l x) v r
    else if x > v then Node l v (insert r x)
    else t
}

contains t x = case t {
  Empty -> False
  Node l v r ->
    if x == v then True
    else if x < v then contains l x
    else contains r x
}

to_list t = case t {
  Empty -> []
  Node l v r -> List.append (to_list l) (v :: to_list r)
}

main () = {
  let t = List.foldl insert Empty [5, 3, 7, 1, 4, 6, 8]
  to_list t |> dbg
  contains t 4 |> dbg
  contains t 9 |> dbg
}