Binary Trees with ReScript

type rec tree<'a> =
  | Leaf
  | Node('a, tree<'a>, tree<'a>)

let rec height = (tree) => {
  switch tree {
  | Leaf => 0
  | Node(_, left, right) => 1 + max(height(left), height(right))
  }
}

let rec insert = (tree, item) => {
  let (key, value) = item
  switch tree {
  | Leaf => Node((key, value), Leaf, Leaf)
  | Node(this, left, right) =>
      let (_key, _) = this
      if key < _key {
        Node(this, insert(left, item), right)
      } else {
        Node(this, left, insert(right, item))
      }
  }
}

let rec search = (tree, key) => {
  switch tree {
  | Leaf => None
  | Node(this, left, right) =>
      let (_key, _value) = this
      if _key == key { Some(_value) }
      else {
        if key < _key { search(left, key) }
        else { search(right, key) }
      }
  }
}

let () = {
  let tree = Leaf
  let tree = insert(tree, (1, "one"))
  let tree = insert(tree, (2, "two"))
  let tree = insert(tree, (3, "three"))
  let tree = insert(tree, (4, "four"))
  let tree = insert(tree, (5, "five"))

  let res = search(tree, 2)
  switch res {
  | None => Js.log("not-found")
  | Some(s) => Js.log(s)
  }
}

Set of Elements

type rec tree<'a> =
  | Leaf
  | Node('a, tree<'a>, tree<'a>)

let rec height = (tree) => {
  switch tree {
  | Leaf => 0
  | Node(_, left, right) => 1 + max(height(left), height(right))
  }
}

let rec insert = (tree, elem) => {
  switch tree {
  | Leaf => Node(elem, Leaf, Leaf)
  | Node(_elem, left, right) =>
      if elem < _elem {
        Node(_elem, insert(left, elem), right)
      } else {
        Node(_elem, left, insert(right, elem))
      }
  }
}

let rec exists = (tree, elem) => {
  switch tree {
  | Leaf => false
  | Node(_elem, left, right) =>
      if _elem == elem { true }
      else {
        if elem < _elem { exists(left, elem) }
        else { exists(right, elem) }
      }
  }
}

let () = {
  let tree = Leaf
  let tree = insert(tree, "one")
  let tree = insert(tree, "two")
  let tree = insert(tree, "three")
  let tree = insert(tree, "four")
  let tree = insert(tree, "five")

  let res = exists(tree, "one")
  switch res {
  | false => Js.log("not-found")
  | true => Js.log("\"one\" exists in the binary tree.")
  }
}

find function

let rec find = (tree, predicate) => {
  switch tree {
  | Leaf => false
  | Node(elem, left, right) =>
      if predicate(elem) { true }
      else {
        find(left, predicate)
        || find(right, predicate)
      }
  }
}

let () = {
  let tree = Leaf
  let tree = insert(tree, "one")
  let tree = insert(tree, "two")
  let tree = insert(tree, "three")

  let res = find(tree, (elem) => elem == "three")
  switch res {
  | false => Js.log("not-found")
  | true => Js.log("found: \"three\"")
  }
}

$ bsc tree2.res > tree2.js
$ node tree2.js
found: "three"

fold function

let rec fold = (tree, param, f) => {
  switch tree {
  | Leaf => param
  | Node(elem, left, right) =>
      let param = f(param, elem)
      let param = fold(left, param, f)
      let param = fold(right, param, f)
      param
  }
}

let () = {
  let tree = Leaf
  let tree = insert(tree, 1)
  let tree = insert(tree, 2)
  let tree = insert(tree, 3)
  let tree = insert(tree, 4)
  let tree = insert(tree, 5)
  let tree = insert(tree, 6)

  let result = fold(tree, 0, (param, elem) => { param + elem } )
  Js.log("result: " ++ Belt.Int.toString(result))
}

$ bsc tree3.res > tree3.js
$ node tree3.js
result: 21

Number of Elements

let rec num = (tree) => {
  switch tree {
  | Leaf => 0
  | Node(_, left, right) =>
      let n1 = num(left)
      let n2 = num(right)
      1 + n1 + n2
  }
}

let () = {
  let tree = Leaf

  let tree = insert(tree, 1)
  let tree = insert(tree, 2)
  let tree = insert(tree, 3)
  let tree = insert(tree, 4)
  let tree = insert(tree, 5)
  let tree = insert(tree, 6)

  let result = num(tree)
  Js.log("number of elements: " ++ Belt.Int.toString(result))
}

number of elements: 6