Pfthb

Please, how do I make this function return the value of every branch and leaf as a float list? I have tried several methods with Tail recursion but I am not able to return the head I cannot loop through the branch and leaf.

type 'a Tree = | Leaf of 'a | Branch of 'a Tree * 'a Tree

let medianInTree (lst: float Tree) :float list=
 let rec medianInTree' (a : float Tree) acc = 
 match lst with
 | Leaf(n) -> n :: acc
 | Branch(Leaf(xx), Leaf(xs)) -> xx :: [xs] 
 | Branch(Leaf(x), Branch(Leaf(xx), Leaf(xs))) -> 
 let acc = medianInTree'(Leaf(x)) acc
 medianInTree' (Branch(Leaf(xx), Leaf(xs))) acc 
 | Branch(_, _) -> 
 medianInTree' lst 

Question: medianInTree (Branch(Leaf(2.0), Branch(Leaf(3.0), Leaf(5.0))))

I want this result: [2.0;3.0;5.0]

using an accumulator, you can do something like this:

let flatten tree =
 let rec toList tree acc =
 match tree with
 | Leaf a -> a :: acc
 | Branch(left, right) ->
 let acc = toList left acc
 toList right acc
 toList tree |> List.rev

But doing so, the recursive call to process the left branch is not tail recursive.
To insure tail recursion while processing tree structures, you have to use continuations.

let flatten tree = 
 let rec toList tree cont acc =
 match tree with
 | Leaf a -> cont (a :: acc)
 | Branch(left, right) -> toList left (fun l ->
 toList right (fun r -> 
 cont r) (cont l)) acc
 toList tree id |> List.rev

Which can be simplified as:

let flatten tree = 
 let rec toList tree cont acc =
 match tree with 
 | Leaf a -> cont (a :: acc)
 | Branch (left, right) -> toList left (toList right cont) acc
 toList tree id |> List.rev

Your main bug is using match with lst instead of on a. I made it a bit simpler as well.

let medianInTree (lst: float Tree) :float list=
 let rec medianInTree' (a : float Tree)= 
 match a with
 | Leaf(n) -> [n]
 | Branch(l, r) -> (medianInTree' l) @ (medianInTree' r)
 medianInTree' lst