Reason BST Blog Post full implementation

ReasonBSTFull.re

type binarySearchTree('a) =
  | Empty
  | Node(node('a))
and node('a) = {
  value: 'a,
  left: binarySearchTree('a),
  right: binarySearchTree('a),
};

let compare = (f, s) =>
  if (f < s) {
    (-1);
  } else if (f > s) {
    1;
  } else {
    0;
  };

let rec insert = (tree, compare, v) =>
  switch (tree) {
  | Empty => Node({value: v, left: Empty, right: Empty})
  | Node({value, left, right}) =>
    if (compare(v, value) == (-1)) {
      Node({value, left: insert(left, compare, v), right});
    } else if (compare(v, value) == 1) {
      Node({value, left, right: insert(right, compare, v)});
    } else {
      tree;
    }
  };

let rec min = node =>
  switch (node) {
  | Empty => Empty
  | Node({value, left, right}) =>
    if (left == Empty) {
      node;
    } else {
      min(left);
    }
  };

let rec max = node =>
  switch (node) {
  | Empty => Empty
  | Node({value, left, right}) =>
    if (right == Empty) {
      node;
    } else {
      max(right);
    }
  };

let rec traverseInOrder = (node, cb) =>
  switch (node) {
  | Empty => ();
  | Node({value, left, right}) =>
    traverseInOrder(left, cb);
    cb(value);
    traverseInOrder(right, cb)
  };

let rec traversePostOrder = (node, cb) =>
  switch (node) {
  | Empty => ()
  | Node({value, left, right}) =>
    traversePostOrder(left, cb);
    traversePostOrder(right, cb);
    cb(value)
  };

let rec traversePreOrder = (node, cb) =>
  switch (node) {
  | Empty => ()
  | Node({value, left, right}) =>
    cb(value);
    traversePreOrder(left, cb);
    traversePreOrder(right, cb);
  };

let rec search = (node, compare, v) =>
  switch (node) {
  | Empty => false
  | Node({value, left, right}) =>
    if (compare(v, value) == (-1)) {
      search(left, compare, v);
    } else if (compare(v, value) == 1) {
      search(right, compare, v);
    } else {
      true;
    }
  };

let rec remove = (tree, compare, v) =>
  switch (tree) {
  | Empty => Empty
  | Node({value, left: Empty, right: Empty}) =>
    compare(v, value) == 0 ? Empty : tree
  | Node({value, left: Node(_) as left, right: Empty as right}) =>
    compare(v, value) == 0 ?
      left : Node({value, left: remove(left, compare, v), right})
  | Node({value, left: Empty as left, right: Node(_) as right}) =>
    compare(v, value) == 0 ?
      right : Node({value, left, right: remove(right, compare, v)})
  | Node({value, left: Node(_) as left, right: Node(_) as right}) =>
    if (compare(v, value) == (-1)) {
      Node({value, left: remove(left, compare, v), right});
    } else if (compare(v, value) == 1) {
      Node({value, left, right: remove(right, compare, v)});
    } else {
      switch (min(right)) {
      | Empty => tree
      | Node(a) =>
        Node({value: a.value, left, right: remove(right, compare, a.value)})
      };
    }
  };

let empty = Empty;
let bst = Node({value: 1, left: Empty, right: Empty});
Js.log(insert(insert(bst, compare, 5), compare, 0));