# Breadth first search printing twice

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

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) ->
(* 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).

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?

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.

Thanks for explaining that - makes full sense now.

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