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