// Code from Hansen and Rischel: Functional Programming using F# 16/12 2012
// Chapter 6: Finite trees.
// Just from Section 6.4 Traversal of binary trees. Search trees
type BinTree<'a when 'a : comparison> =
| Leaf
| Node of BinTree<'a> * 'a * BinTree<'a>;;
let rec preOrder = function
| Leaf -> []
| Node(tl,x,tr) -> x :: (preOrder tl) @ (preOrder tr);;
let rec inOrder = function
| Leaf -> []
| Node(tl,x,tr) -> (inOrder tl) @ [x] @ (inOrder tr);;
let rec postOrder = function
| Leaf -> []
| Node(tl,x,tr) -> (postOrder tl) @ (postOrder tr) @ [x];;
let rec postFoldBack f t e =
match t with
| Leaf -> e
| Node(tl,x,tr) ->
let ex = f x e
let er = postFoldBack f tr ex
postFoldBack f tl er;;
let rec add x t =
match t with
| Leaf -> Node(Leaf,x,Leaf)
| Node(tl,a,tr) when x Node(add x tl,a,tr)
| Node(tl,a,tr) when x>a -> Node(tl,a,add x tr)
| _ -> t;;
let rec contains x = function
| Leaf -> false
| Node(tl,a,_) when x contains x tl
| Node(_,a,tr) when x>a -> contains x tr
| _ -> true;;