Binary tree Breadth-first search

Question

I'm using OCaml. I have type:

type 'a bt = Empty | Node of 'a * 'a bt * 'a bt;;

Also I have example BST:

let tree = Node(1,Node(2,Node(4,Empty,Empty),Empty),Node(3,Node(5,Empty,Node(6,Empty,Empty)),Empty));

I need to write function: breadthBT : 'a bt -> 'a list which will be Breadth-first search traversal. For above example tree it should returns [1; 2; 3; 4; 5; 6]

How to write that function? I can write only following function which uses DST :

let rec breadthBT tree =
if tree=Empty then []
else let Node(w,l,r)=tree in (w::breadthBT l)@breadthBT r;;

Above function returns (for example tree) [1; 2; 4; 3; 5; 6]. But I can't write function which uses BFS. Could you help me?

Answer 1

It is not a compilable solution. Just a tip. You should iterate from top level root node to deep level nodes. Let our function receives accumulator for the answer and list of nodes (your 'a bt values) as second parameter. You can map this list by getting first element of triple and than you receive next part of answer. Also you need to evaluate next level of tree. For every node there are at most two descendants. You can map your list and apply _a_function_to receive list of descendants. It will be next level of your tree. And than --- recursion.

A will not specify this _a_function_. Try to study what is concatMap in google.

Happy hacking!