Deleting a node from Binary Tree in OCaml

Question

I am currently exploring OCaml and wrote the following implementation of deleting a node from a binary tree

let rec deleteNode tree' value = 
  match tree' with 
  | Empty -> Empty
  | Node(left, nodeValue, right) -> 
      if value < nodeValue then
        Node((deleteNode left value), nodeValue, right)
      else if value > nodeValue then 
        Node(left, nodeValue, (deleteNode right value))
      else if left = Empty && 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))

Where my tree type is

type tree = 
  | Empty
  | Node of tree * int * tree

I am looking for a review of my code so that I can improve my OCaml and functional skills.

Answer 1

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 ->.

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

let rec deleteNode tree' value = 
  match tree' with 
  | Empty -> Empty
  | Node (left, nodeValue, right) when value < nodeValue ->
        Node((deleteNode left value), nodeValue, right)
  | Node (left, nodeValue, right) when value > nodeValue ->
        Node(left, nodeValue, (deleteNode right value))
  | Node (left, nodeValue, right) -> 
      if left = Empty && 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 -> Empty
  | Node (left, nodeValue, right) when value < nodeValue ->
        Node((deleteNode left value), nodeValue, right)
  | Node (left, nodeValue, right) when value > nodeValue ->
        Node(left, nodeValue, (deleteNode right value))
  | Node (Empty, nodeValue, Empty) -> 
        Empty
  | Node (Empty, nodeValue, right) -> 
        right
  | Node (left, nodeValue, Empty) -> 
        left
  | Node (left, nodeValue, right) -> 
        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.