// [snippet:Type definition]
type 'a binary_tree =
    | Empty
    | Node of 'a * 'a binary_tree * 'a binary_tree

let example_tree =
    Node('a', Node('b', Node('d', Empty, Empty), Node('e', Empty, Empty)),
         Node('c', Empty, Node('f', Node('g', Empty, Empty), Empty)))
// [/snippet]

// [snippet:Counting leaves]
let rec count_leaves tree =
    match tree with
        | Empty -> 0
        | Node(_,Empty,Empty) -> 1
        | Node(_,a,b) -> (count_leaves a) + (count_leaves  b)
// [/snippet]

// [snippet:Generating layout]
type 'a pos_binary_tree =
    | E (* represents the empty tree *)
    | N of 'a * int * int * 'a pos_binary_tree * 'a pos_binary_tree 
    (*N(w,x,y,l,r) represents a (non-empty) binary tree with root w "positioned" at (x,y), and subtrees l and r *)

let make_pos_binary_tree  (tree:binary_tree<_>) =
    let rec layout t x depth =
        match t with
            | Empty -> (x,E)
            | Node(a,l,r) ->
                let x',lTree = layout l x (depth+1)
                let x'',rTree = layout r (x'+1) (depth+1)
                (x'',N(a,x',depth,lTree,rTree))
    let finalX,finalTree = layout tree 1 1
    finalTree
// [/snippet]

// [snippet:Example and rendering]
let laidOutTree = make_pos_binary_tree example_tree

let canvas = Array2D.init 50 50 (fun _ _ -> ' ')

let rec draw tree =
    match tree with
        | E -> ()
        | N(v,x,y,l,r) ->
            canvas.[y,x] <- v
            draw l
            draw r

draw laidOutTree

for y in 0..49 do
    for x in 0..49 do
        stdout.Write(canvas.[y,x])
    stdout.WriteLine()
// [/snippet]