Random AST generation with the specified size in Clojure

I would like to generate a random abstract syntax tree

(def terminal-set #{'x 'R})
(def function-arity {'+ 2, '- 2, '* 2, '% 2})
(def function-set (into #{} (keys function-arity)))
(def terminal-vec (into [] terminal-set))
(def function-vec (into [] function-set))

;; protected division
(defn % [^Number x ^Number y]
  (if (zero? y)
    0
    (/ x y)))

with the specified size

(defn treesize [tree] (count (flatten tree)))

following the algorithm from the book Sean Luke, 2013, Essentials of Metaheuristics, Lulu, second edition, available at https://cs.gmu.edu/~sean/book/metaheuristics/

We randomly extend the horizon of a tree with nonleaf nodes until the number of nonleaf nodes, plus the remaining spots, is greater than or equal to the desired size. We then populate the remaining slots with leaf nodes:

My note: the algorithm is basically about filling the nodes in breadth-first fashion until the size limit is met.

For example

(+ (* x (+ x x)) x)

is of size 7.

The algorithm in the book uses pointers/references Q which is very convenient there. In my case I have to use some kind of recursion to construct the tree. The problem is that I can't keep the state size of the tree between all algorithms using recursion which results in larger trees:

(defn ptc2-tree
  "Generate a random tree up to its `max-size`.
  Note: `max-size` is the number of nodes, not the same as its depth."
  [max-size]
  (if (> 2 max-size)
    (rand-nth terminal-vec)
    (let [fun   (rand-nth function-vec)
          arity (function-arity fun)]
      (cons fun (repeatedly arity #(ptc2-tree (- max-size arity 1)))))))

I also tried using atom for size but still couldn't get the exact tree size I want, it was either too small or too big depending on implementation.

How do I write this algorithm?