1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
public int randomInt(final int min, final int max) {
    return (int)(min + Math.random() * (max - min + 1));
}

public Node randomTree() {
    var roots = new ArrayList<Node>();
    for (int i = 0; i < randomInt(0, 100); i++)
        roots.add(new Node(randomInt(0, 100), null, null));
    if (roots.isEmpty())
        return null;
    int depth = 1;
    for (; roots.size() > 1; depth++) {
        // Each iteration of this loop adds one level to the tree.
        // Each level must have at least half rounded up as many nodes as there were on the level below.
        // A level could have more nodes than the level below it, but usually won't.
        Collections.shuffle(roots);
        var newRoots = new ArrayList<Node>();
        while (!roots.isEmpty()) {
            // Each iteration of this loop adds one node to the level.
            int childCount = 1;
            if (roots.size() > 1) {
                childCount = randomInt(0, 4);
                if (childCount >= 2)
                    childCount = 2;
            }
            if (childCount == 0)
                newRoots.add(new Node(randomInt(0, 100), null, null));
            else if (childCount == 2)
                newRoots.add(new Node(randomInt(0, 100), roots.remove(0), roots.remove(0)));
            else {
                if (randomInt(0, 1) == 0)
                    newRoots.add(new Node(randomInt(0, 100), roots.remove(0), null));
                else
                    newRoots.add(new Node(randomInt(0, 100), null, roots.remove(0)));
            }
        }
        roots = new ArrayList<>(newRoots);
        newRoots.clear();
    }
    return roots.get(0);
}