F# How to Flatten a Binary Search Tree

Question

I have a tree, structured as :

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

I am using continuation-passing style tail recursion over my tree and trying to flatten it.

let rec loop tree k acc = 
  match tree with
  | Leaf v -> v :: acc
  | Branch (tl,tr) -> loop tl (loop tr k) acc
loop xs id []


(Branch (Branch (Leaf 1.0,Leaf 2.0),Branch (Leaf 3.0,Leaf 4.0)))

This returns only [1.0]

However I only get the first leaf in a tree, my function does not work on an entire tree. How can I achieve that?

Answer 1

You're passing in a continuation, but you're not calling it anywhere. Try this:

let rec loop tree k acc = 
  match tree with
  | Leaf v -> k (v :: acc)
  | Branch (tl,tr) -> loop tl (loop tr k) acc

Then loop xs id [] produces [4.0; 3.0; 2.0; 1.0].