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
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:
Post a Comment