# Deleting a node from Binary Tree in OCaml

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.

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