Deleting a node from Binary Tree in OCaml
Syntax

There are no hard rules on this, but I would change a couple things in your syntax:


avoid ' in identifiers. Especially in that case, you can use tree instead of tree' (there is no collision with the type name).
usually there's a space before constructor arguments, like Node (left, nodeValue, right) (really up to convention, but I'd say it's more common).
parentheses around function application are not necessary, so it's more idiomatic to write Node (deleteNode left value, nodeValue, right). You can also extract a binding: let newLeft = deleteNode left value in Node (newLeft, nodeValue, right)
camel case is rare is ocaml (I know, that's weird!). For example the standard library uses names like print_endline etc. So, I'd use node_value, etc.


Replace conditionals with guards

Every time a if is in a pattern matching branch, you can extract it into a guard. The syntax is | pattern when condition -&gt;.

By applying this to the first ifs, we can arrive to this state:

let rec deleteNode tree' value = 
  match tree' with 
  | Empty -&gt; Empty
  | Node (left, nodeValue, right) when value &lt; nodeValue -&gt;
        Node((deleteNode left value), nodeValue, right)
  | Node (left, nodeValue, right) when value &gt; nodeValue -&gt;
        Node(left, nodeValue, (deleteNode right value))
  | Node (left, nodeValue, right) -&gt; 
      if left = Empty &amp;&amp; right = Empty then 
        Empty
      else if left = Empty then 
        right
      else if right = Empty then
        left
      else 
        let newValue = minValue right in
        Node(left, newValue, (deleteNode right newValue))


Use deep pattern matching

You can replace the x = Empty tests by pattern matching. In other words, patterns can contain patterns. By applying this to all the conditionals, we get:

let rec deleteNode tree' value = 
  match tree' with 
  | Empty -&gt; Empty
  | Node (left, nodeValue, right) when value &lt; nodeValue -&gt;
        Node((deleteNode left value), nodeValue, right)
  | Node (left, nodeValue, right) when value &gt; nodeValue -&gt;
        Node(left, nodeValue, (deleteNode right value))
  | Node (Empty, nodeValue, Empty) -&gt; 
        Empty
  | Node (Empty, nodeValue, right) -&gt; 
        right
  | Node (left, nodeValue, Empty) -&gt; 
        left
  | Node (left, nodeValue, right) -&gt; 
        let newValue = minValue right in
        Node(left, newValue, (deleteNode right newValue))


 Remove redundant cases

That's more obvious with pattern matching, but the Node (Empty, nodeValue, right) cases also applies when right = Empty, so we can delete the more specific Node (Empty, nodeValue, Empty) case.

That's about it! Have a nice journey exploring OCaml.