f# access root element of a tree

I have a canonical tree in F#, i.e by declaring

type binaryTree = 
    | Leaf
    | Node of binaryTree * float * binaryTree

and then using a recursive function to make the tree

let rec makeTree tree element = 
    match element, tree with
        | x, Leaf -> Node(Leaf,x,Leaf)
        | x, Node(l,y,r) -> Node(l,y, (makeTree r x))

This is all fine. Now I want to sort the tree so that at each node, the value of the node is smaller than the value of all its children. I can imagine doing this. However, I want to then take the first element of the tree. That is, I want to treat the tree like a queue. The only examples I have seen with trees use higher-order functions to do something with the tree, but this seems like a waste when I have already sorted it.

How can I a开发者_开发问答ccess the root node of this tree?

---

How about this:

let rootValue (Node(_,v,_)) = v

This will throw an exception if the tree is empty. Alternatively:

let tryGetRootValue = function
| Node(_,v,_) -> Some v
| _ -> None

This will always succeed, but will return a float option rather than a float.

---

The question is a bit unclear. As I understand it, you'll have a tree where the value of node is smaller than the value of its children. (Which you can implement by sorthing the tree or by writing a different function that constructs it such that this is true.)

To implement a function that takes the first (smallest) element of the tree, you need to remove the root (which is smallest) and then merge the two trees you'll get. This can be done by taking the smaller of the two roots as the new root and recursively merging the new trees you'll get. The following snippet should do the trick:

let rec merge t1 t2 = 
  match t1, t2 with
  | Leaf, t | t, Leaf -> t // Merging a tree and a leaf gives the tree
  | (Node(ll, x1, lr) as t1), (Node(rl, x2, rr) as t2) ->
      // When merging two trees, take the smaller root as a new root
      // This gives you three new trees, so two of them must be recursively merged
      if x1 < x2 then Node(merge ll lr, x1, t2)
      else Node(t1, x2, merge rl rr)

let rec tryTake tree = 
  match tree with
  | Leaf -> None
  | Node(t1, y, t2) -> Some(y, merge t1 t2)