type Tree =
    | Empty
    | Node of value:char * weight:int * left:Tree * right:Tree

let countOccurrances str =
    str|>Seq.countBy id

let createLeaves occ =
    occ|> Seq.map (fun (c,w) -> Node(c, w, Empty, Empty))

let sortByWeight t =
        match t with
        |Node(_,w,_,_) -> w
        |Empty -> failwith "Empty Nodes"

let rec buildTree leaves =
    match Seq.length leaves with
    |1 -> Seq.head leaves
    |_ ->
        let nodes = leaves |> Seq.sortBy sortByWeight
        let left = Seq.item 1 nodes
        let right = Seq.head nodes
        match (left, right) with
        |(Node(_,w1,_,_), Node(_,w2,_,_)) -> Seq.skip 2 nodes |> Seq.append [Node('\n', w1+w2, left, right)] |> buildTree
        |_ -> failwith "Empty Nodes"

let rec printTree bitString root =
    match root with
    |Node(v,_,l,r) ->
        match (l,r) with
        |(Node(_,_,_,_), Node(_,_,_,_)) ->
            printTree (Seq.append bitString [1]) l
            printTree (Seq.append bitString [0]) r
        |_ ->
            let str =
                match Seq.length bitString with
                |0 -> Seq.init 1 (fun i -> i)
                |_ -> bitString
            printfn "%A : %c" str v
    |_ -> failwith "Root is Empty"

"aaaaaaaabbbbccd" |> countOccurrances |> createLeaves |> buildTree |> printTree Seq.empty