Problem description
===================

I am trying to write a math test for my little son.
Such test must generate a list of random algebraic expressions according to certain rules and check the correctness of solution.

In particular, I want to generate expressions consisting strictly of a given number of operators that are selected from a certain list.
For example *generate a list of expression consisting of 3 operators of addition and subtraction in random order* like:

* 12 - (5 + 2) + 2
* 3 + 4 - 2 + 10
* and so on

To represent and calculate the expression, I use the *binary expression tree* structure.
Each tree consists of either a `Leaf` or a `Node` that contains an `Operator` and two subtrees.
This is a simple recursive structure and I want to work with it only recursively.
No setters in the classes of the tree. I can only use constructors to create a tree.

#### Leaf class

```
public final class Leaf implements Expression {

    private final int value;

    public Leaf(int value) {
        this.value = value;
    }

    // ...
}

```

#### Node Class

```
public final class Node implements Expression {

    private final Operator operator;
    private final Expression left;
    private final Expression right;

    public Node(@NotNull Operator operator, 
                @NotNull Expression left,
                @NotNull Expression right) {
        this.operator = operator;
        this.left = left;
        this.right = right;
    }

    // ...
}

```

And `Operator` is a simple `Enum` type. I simplify my classes for the purposes of this question.

My issue
========

I am trying to build an expression based on the following rules:

* There should be at least one operator in the expression, so my tree always starts from the `Node`.
* I choose a random operator from a given list and increase the number of operators used
* While this number less than the given number of operators I construct the left and rights subtree for current `Node`.
* The left subtree can be randomly either a `Leaf` or `Node`
* The right subtree can also be either a `Leaf` or `Node`, but if the left subtree is a `Leaf` and there are still unused operators, then the right must be a `Node`.

I wrote such an expression builder:

```
public class SmartExpressionBuilder {

    private final Random random = ThreadLocalRandom.current();
    private final List<Operator> allowedOperators;
    private final int numberOfOperators;

    public SmartExpressionBuilder(List<Operator> allowedOperators, int numberOfOperators) {
        this.allowedOperators = allowedOperators;
        this.numberOfOperators = numberOfOperators;
    }

    private int operatorsUsed;

    public Expression build() {
        operatorsUsed = 0;
        return helper();
    }

    private Expression helper() {
        if (operatorsUsed == numberOfOperators) return randomLeaf();

        Operator op = randomOperator();

        Expression left = random.nextBoolean() ? helper() : randomLeaf();
        Expression right = (left instanceof Leaf || random.nextBoolean()) ? helper() : randomLeaf();

        return new Node(op, left, right);
    }

    private Operator randomOperator() {
        operatorsUsed++;
        return allowedOperators.get(random.nextInt(allowedOperators.size()));
    }

    private Leaf randomLeaf() {
        return new Leaf(random.nextInt(1, 10));
    }

    public static void main(String[] args) {
        final var builder = new SmartExpressionBuilder(List.of(Operator.ADD, Operator.SUB), 4);
        IntStream.range(0, 10)
                .mapToObj(ignored -> builder.build())
                .forEach(exp -> {
                    System.out.printf("%s = %d%n", exp.infix(), exp.evaluate());
                    TreePrinter.print(exp);
                });
    }
}

```

This works in principle. In the sense that a tree really builds with a given number of operators.
But there's a problem.
I get nodes looks like this:

```
    Node                Node
   /    \      or      /    \
 Leaf  Node          Node  Leaf

```

For example my actual expression and tree may looks like this:

```
4 + 4 - (1 + 3) - 2 = 2
            +
    4               -
                -       2
              4   +        
                 1 3        

```

but i never get tree like this:

```
    Node                  +
   /    \        or    -     +
 Node  Node           5 2  2   -
                              6 1

```

I understand what the essence of the problem is.
In my recursive function, I always go into the left tree first.
And every time my random generates an the `Node` is in the left subtree, and not the `Leaf`, recursion dive deeper and deeper int the left subtree until unused operators ends.
This means that if an `Node` appeared in the left subtree, then `Node` cannot appear in the right at the same depths of tree.

I broke my brain, but did not figure out how to solve this problem without abandoning the recursive construction of my tree.

I would be very grateful for any ideas how build nodes of this kind

```
    Node
   /    \
 Node  Node

```