Breadth first search printing twice

Learning
1

Hi,
I am trying something rudimentary for a BFS using pattern matching. Here is the example:

type 'a tree =
| Leaf
| Node of 'a * 'a tree * 'a tree

let t =
Node(4,
Node(2,
Node(1, Leaf, Leaf),
Node(3, Leaf, Leaf)
),
Node(5,
Node(6, Leaf, Leaf),
Node(7, Leaf, Leaf)
)
)

let rec bdd t q = match t with
| Leaf → “”
| Node (i,t1,t2) → let w,(),() = (Queue.pop q,Queue.add t1 q, Queue.add t2 q) in string_of_int(i)^" "^bdd w q
let q1 = Queue.create()

let () = Queue.add t q1

let ss = bdd t q1

let () = print_string ss

The output I expected was 4 2 5 1 3 6 7. The output I get is 4 4 2 5 2 5 1 3 6 7 1 3 6 7
Note: I took the tree example from here: 3.11. Example: Trees — OCaml Programming: Correct + Efficient + Beautiful

I am trying to use the builtin queue for BFS - to simply learn more

2

You should not take at the same time the queue q and the tree t. It looks like you are mixing two things, the traversal of a tree and a BFS of the tree.

As if you were to write it with a while loop, your base case should be when your queue is empty, not when you encounter a Leaf (in that case, just do not add anything to q but still call yourself recursively, maybe there are still trees in the queue). So your function should look something like:

let rec bdd q =
   if Queue.is_empty q then (* do something in the base case *)
   else match Queue.pop q with
             Leaf -> bdd q
            | Node (i, t1, t2) ->
                Queue.add t1 q;
                Queue.add t2 q;
                 (* do something with i  *)
                bdd q

Other things are wrong with your code. First, the order of evaluation of a tuple is unspecified, you should not write (e1, e2, e3) where the expressions perform side-effects (since it so happens that in practice e3 will be evaluated first and e1 last). You should use let in to evaluate them in the correct order.
Furthermore here, the two Queue.add return (), you can just put them in sequence with a ;.

Lastly concatenating strings might become inefficient. You should rather use a Buffer.t and append to it while performing your BFS (but this may become irrelevant if you are just building the string to debug your function).

3

Thanks for replying. This definitely solves the issue, but the following is not clear to me. I try with this modification:

| Node (i,t1,t2) -> let w = Queue.pop q in Queue.add t1 q; Queue.add t2 q; string_of_int(i)^" "^(bdd w q)

To ensure that they happen in sequence, still, I see the output 4 4 2 5 2 5 1 3 6 7 1 3 6 7. What is making this repeat twice?

4

I don’t know how you modified the whole function, but you should not pop the queue after the match.
Otherwise you are processing the original tree twice, hence the behavior you observe. If you look at your original code, let’s call t0 the whole example tree.

  1. you create a queue q and add t0 to it. Then you call bdd t0 q
  2. in bdd you match on t0 so you will add it subtrees to the queue
  3. in the Node ... -> branch, you pop from the queue (hence w is again t0) and you call bdd w q.

So clearly your function is called twice on the root of the tree which is wrong.

5

Thanks for explaining that - makes full sense now.

Also, I had a question about using the buffer_t to concatenate strings. Could please share a link where I can learn more about it?

6

You can look at the documentation for the Buffer module here. It is similar to Java’s StringBuffer class.