Algorithm that checks if a tree is full and complete
On the whole I like your implementation. It is elegant and correct. I also like your use of a TreeInfo object.

Your calculation of valid is a little unnecessarily complex - you can make it much simpler and clearer as a single statement.

You may find (and this is only my opinion) adding some comments helps you think more clearly about the code.

Once I had finished tinkering my version looks like:

public boolean isFullCompleteTree(Tree&lt;Integer&gt; t) {
    TreeInfo rootInfo = isFullCompleteTree(t.getRoot());
    return rootInfo.valid;
}

public TreeInfo isFullCompleteTree(Node&lt;Integer&gt; node) {

    if (node == null) {
        // A null node is valid with a size of 0.
        return new TreeInfo(true, 0);
    }

    // Inspect both branches.
    TreeInfo rightInfo = isFullCompleteTree(node.goRight());
    TreeInfo leftInfo = isFullCompleteTree(node.goLeft());

    // Valid when both branches are valid and have the same child count.
    boolean valid = rightInfo.valid &amp;&amp; leftInfo.valid
            &amp;&amp; rightInfo.numChildern == leftInfo.numChildern;
    return new TreeInfo(valid, 
            // My size is the total size of my children + 1
            rightInfo.numChildern + leftInfo.numChildern + 1);
}


Notice how the valid calculation matches your spec of its left son has number of children that is equal to its right son's number of children along with the obvious both children are valid.