Sunday, October 14, 2012

F# on Algorithms - Build BST from Pre-order


I guess everyone familiar with building a tree from pre-order and in-order. But for BST, we only need a pre-order. 

type NodeType = int

type BinaryTree =
    | Nil
    | Node of NodeType * BinaryTree * BinaryTree

let rec buildBSTfromPreOrder (l:NodeType list) =
    match l with
    | [] -> Nil
    | [a] -> Node(a, Nil, Nil)
    | h::t ->
        let smaller =
                   t
                   |> Seq.takeWhile (fun n -> n < h)
                   |> Seq.toList
        let bigger =
                   t
                   |> Seq.skipWhile (fun n -> n < h)
                   |> Seq.toList
        Node(h, buildBSTfromPreOrder(smaller), buildBSTfromPreOrder(bigger))

let input = [10; 5; 1; 7; 40; 50]
buildBSTfromPreOrder input

No comments: