CODEWITHSUNDEEP
ocamlbinary-tree
Paul
Paul

Reputation: 2007

Binary tree Breadth-first search

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?

Upvotes: 6

Views: 3062

Answers (2)

lukstafi
lukstafi

Reputation: 1895

Imagine you stick your nose to the tree. Is it possible to traverse the tree in the breadth-first manner without bookmarking positions in your notepad? No, because the order can make you jump from one branch to another unrelated branch. So you need a notepad with "remaining positions to visit". You pick the next remaining position from the notepad and jump to it blindly. Since you erase visited positions from the notepad, you are at a node you have not visited yet. And since you cannot get up the tree without visiting intermediate nodes, you haven't visited the two nodes now above you. But you resist the instinct to climb the branches directly -- heck, this is breadth first order. You do not want to forget about these two unvisited nodes, so you want to put them into the notebook. Where do you put them, in front of the notebook or on its back? On the back of course, otherwise you would pick one of them immediately and that's what we want to avoid. Et voila: your notepad is a FIFO queue of nodes, which you keep (i.e. pass) around as an accumulator, but also consume to pick a subtree to visit.

Upvotes: 1

Kakadu
Kakadu

Reputation: 2839

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!

Upvotes: 5

Related Questions