Binary Tree Insertion

type 'a tree
  = Empty
  | Node of 'a * 'a tree * 'a tree

A binary tree is ordered if, given Node (a, left, right), every element of left is at most a and every element of right is greater than a. Repetitions are allowed.

Implement the function

val insert : 'a -> 'a tree -> 'a tree

so that insert x t, given an ordered tree t, is an ordered tree with the same elements as t along with the new element x.

Challenge worth nothing: Make your implementation tail recursive.

let _ = assert (insert 5 Empty = Node (5, Empty, Empty))

let t = Node (5, Empty, Empty)
let _ = assert (insert 3 t = Node (5, Node (3, Empty, Empty), Empty))
let _ = assert (insert 8 t = Node (5, Empty, Node (8, Empty, Empty)))

let _ = assert (insert 4 (insert 8 (insert 3 (insert 5 Empty))) =
    Node (5, Node (3, Empty, Node (4, Empty, Empty)), Node (8, Empty, Empty)))