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.

• Chris: Suggestion: don't bother binding names to patterns that aren't used. E.g. Node (Empty, nodeValue, Empty) -> Empty => Node (Empty, _, Empty) -> Empty