Home

Algorithm Problem #2 Follow-Up #2: Testing the size of generated trees

Context

So far we’ve got a piece of code to compare unordered binary trees and another one to randomly generate strictly binary tree shapes. Now before we’ll put together a property based test around comparing unordered binary trees, we’d like to be sure that generation of trees works fine. In this context “fine” means that:

  1. Only trees of size N are generated for a given N
  2. Every possible shape out of C_n possible shapes can be obtained
  3. Each shape can be obtained with same probability, i.e. distribution is uniform.

Obviously this can also be tested in a property based approach. We’ll start with property 1 which is easiest to verify, but still gives minimum confidence in implementation correctness.

Property 1 - Only trees of size N are generated for a given N

This would be the simple test where for every possible N denoting size of a tree a random tree would be generated, then Leaf nodes would be trimmed to allow for counting and then number of nodes would be counted.

So first we’ll need a Trimmer to remove leaves from a tree. It’ll recursively traverse a tree and remove nodes that have neither left nor right subtree.

Start with boilerplate code of right interfaces for that:

Trimmer.java 
public class Trimmer<K> implements UnaryOperator<Tree<K>> {

    @Override
    public Tree<K> apply(Tree<K> tree) {
        return null;
    }
}

Then inside apply start with handling edge cases on which recursion has to stop, followed by recursive step.

Trimmer::apply 
    @Override
    public Tree<K> apply(Tree<K> tree) {
        if (tree == null) {
            return null;
        }

        if (tree.left() == null && tree.right() == null) {
            return null;
        }

        tree.left(apply(tree.left()));
        tree.right(apply(tree.right()));

        return tree;
    }

Now the leaves are trimmed remaining nodes in a Tree have to be counted, again approaching this in a recursive manner is easiest to implement.

TreeSize.java 
public class TreeSize implements ToIntFunction<Tree<?>>, Function<Tree<?>, Integer> {

    @Override
    public int applyAsInt(Tree<?> value) {
        if (value == null) {
            return 0;
        }

        return applyAsInt(value.left()) + applyAsInt(value.right()) + 1;
    }

    @Override
    public Integer apply(Tree<?> tree) {
        return applyAsInt(tree);
    }
}

Now putting this all together into a test case will look the following. Start with initializing required test dependencies:

Test Setup 
class RandomTreeRemyTest {

    private final Trimmer<Integer> trimmer = new Trimmer<>();
    private final TreeSize treeSize = new TreeSize();
    private final Random random = new Random();

    private final RandomTreeRemy<Integer> generator = new RandomTreeRemy<>(random);
}

And finally test case itself, utilizing Java functional APIs methods for concise syntax. JQwik defaults to 1000 runs per property, so having upper cap at 65k is just chosen so that test runs reasonably fast on modern machine.

treeGeneratedWithExpectedSize 
    @Property
    void treeGeneratedWithExpectedSize(@ForAll @IntRange(min = 0, max = 65536) int size) {
        Integer actual = generator.andThen(trimmer).andThen(treeSize).apply(size);

        assertThat(actual).isEqualTo(size);
    }

Source Code