(* The data type binary tree *)

datatype 'a bintree =
         Empty |
         Node of 'a * 'a bintree * 'a bintree
;

exception Empty_binary_tree;

fun subtrees (Empty) = raise Empty_binary_tree
|   subtrees (Node(root, left, right)) = (left, right)
;

fun root (Empty) = raise Empty_binary_tree
|   root (Node(ro, le, ri)) = ro
;

fun leftsubtree (Empty) = raise Empty_binary_tree
|   leftsubtree (Node(root, left, right)) = left
;

fun rightsubtree (Empty) = raise Empty_binary_tree
|   rightsubtree (Node(root, left, right)) =  right
;

(* Checking whether a given binary tree is balanced *)

fun depth (Empty) = 0
|   depth (Node(root, left, right)) = 1+max (depth (left), depth (right))
;

(* Here is a simplistic definition of preorder traversal *)

fun preorder1 (Empty) = nil
|   preorder1 (Node (x, left, right)) =
              [x] @ preorder1 (left) @ preorder1 (right)
;

(* The above definition though correct is inefficient because it has
   complexity closer to n^2 since the append function itself is linear in
   the length of the list. We would like an algorithm that is linear in the
   number of nodes of the tree. So here is a new one, which uses an iterative
   auxuliary function that stores the preorder traversal of the right subtree
   and then gradually attaches the preorder traversal of the left subtree
   and finally attaches the root as the head of the list.
*)

fun pre (Empty, L) = L
|   pre (Node (x, left, right), L) =
        let val M = pre (right, L);
            val N = pre (left, M)
        in  x::N
        end
;

fun preorder2 (T) = pre (T, [])
;

(* Similarly let's do inorder and postorder traversal *)

fun inorder1 (Empty) = nil
|   inorder1 (Node (x, left, right)) =
              inorder1 (left) @ [x] @ inorder1 (right)
;
fun ino (Empty, L) = L
|   ino (Node (x, left, right), L) =
        let val M = ino (right, L);
            val N = ino (left, x::M)
        in  N
        end
;

fun inorder2 (T) = ino (T, [])
;

fun postorder1 (Empty) = nil
|   postorder1 (Node (x, left, right)) =
               postorder1 (left) @ postorder1 (right) @ [x]
;
fun post (Empty, L) = L
|   post (Node (x, left, right), L) =
        let val M = post (right, x::L);
            val N = post (left, M)
        in  N
        end
;

fun postorder2 (T) = post (T, [])
;

fun isBalanced (Empty) = true
|   isBalanced (Node(root, left, right)) =
               (abs (depth (left) - depth (right)) <= 1) andalso
               isBalanced (left) andalso isBalanced (right)
;

(* A map function for binary trees *

fun BTmap (F) =
    let fun BTM (Empty) = Empty
        |   BTM (Node (x, left, right)) = Node (F(x), BTM (left), BTM (right))
    in  BTM
    end
;

(* How does one construct balanced binary trees? *)

(* How does one construct complete binary trees? *)