# Breadth first search printing twice

**URL:** <https://discuss.ocaml.org/t/breadth-first-search-printing-twice/13145>\
**Category:** Learning\
**Tags:** queue\
**Created:** [October 2, 2023, 9:11pm UTC](https://discuss.ocaml.org/t/breadth-first-search-printing-twice/13145 "2023-10-02T21:11:34Z")\
**Posts on this page:** 6\
**Page:** 1

<div class="post-metadata">

**Author:** ![gokulhari](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/gokulhari/32/4059_2.png) [@gokulhari](https://discuss.ocaml.org/u/gokulhari)\
**Post date:** [October 2, 2023, 9:11pm UTC](https://discuss.ocaml.org/t/breadth-first-search-printing-twice/13145/1 "2023-10-02T21:11:34Z")

</div>

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](https://cs3110.github.io/textbook/chapters/data/trees.html)

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

---

<div class="post-metadata">

**Author:** ![K\_N](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/k_n/32/2793_2.png) [@K\_N](https://discuss.ocaml.org/u/K_N)\
**Post date:** [October 2, 2023, 10:30pm UTC](https://discuss.ocaml.org/t/breadth-first-search-printing-twice/13145/2 "2023-10-02T22:30:05Z")

</div>

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:

```ocaml
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).

---

<div class="post-metadata">

**Author:** ![gokulhari](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/gokulhari/32/4059_2.png) [@gokulhari](https://discuss.ocaml.org/u/gokulhari)\
**Post date:** [October 3, 2023, 1:56am UTC](https://discuss.ocaml.org/t/breadth-first-search-printing-twice/13145/3 "2023-10-03T01:56:03Z")

</div>

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?

---

<div class="post-metadata">

**Author:** ![K\_N](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/k_n/32/2793_2.png) [@K\_N](https://discuss.ocaml.org/u/K_N)\
**Post date:** [October 3, 2023, 5:39am UTC](https://discuss.ocaml.org/t/breadth-first-search-printing-twice/13145/4 "2023-10-03T05:39:11Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![gokulhari](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/gokulhari/32/4059_2.png) [@gokulhari](https://discuss.ocaml.org/u/gokulhari)\
**Post date:** [October 4, 2023, 2:23am UTC](https://discuss.ocaml.org/t/breadth-first-search-printing-twice/13145/5 "2023-10-04T02:23:15Z")

</div>

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?

---

<div class="post-metadata">

**Author:** ![K\_N](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/k_n/32/2793_2.png) [@K\_N](https://discuss.ocaml.org/u/K_N)\
**Post date:** [October 4, 2023, 7:47pm UTC](https://discuss.ocaml.org/t/breadth-first-search-printing-twice/13145/6 "2023-10-04T19:47:26Z")

</div>

You can look at the documentation for the `Buffer` module [here](https://v2.ocaml.org/releases/5.1/api/Buffer.html). It is similar to Java’s `StringBuffer` class.