Algorithm that checks if a tree is full and complete

I am trying to write a method that will return true if a binary tree is full and complete (each node has 2 children or none and all the leaves of the tree are at the same depth).

My idea is to use recursion. I will check for any node if its left son has number of children that is equal to its right son's number of children. If so, I will return true, otherwise false.

The algorithm will look like this:

public class Utils {

    public boolean isFullCompleteTree(Tree t) {
            TreeInfo rootInfo = isFullCompleteTree(t.getRoot());
            return rootInfo.valid;
        }
    public TreeInfo isFullCompleteTree(Node node) {
        boolean valid = true;

        if (node == null) {
            return new TreeInfo(true, 0);
        }

        TreeInfo rightInfo = isFullCompleteTree(node.goRight());
        TreeInfo leftInfo = isFullCompleteTree(node.goLeft());

        if ((!rightInfo.valid) || (!leftInfo.valid)) {
            valid = false;
        }
        if (rightInfo.numChildern != leftInfo.numChildern) {
            valid = false;
        }
        return new TreeInfo(valid, rightInfo.numChildern + leftInfo.numChildern
                + 1);
    }
    }

    class TreeInfo {
       public boolean valid;
       public int numChildern;

       public TreeInfo(boolean valid, int numChildern) {
           this.valid = valid;
           this.numChildern = numChildern;
    }

}

I didn't include the tree implementation but it is pretty straightforward.

The idea of the algorithm is to check if in every node the number of right son's children is equal to the left son's children. If a tree is not full and complete, then in some node this rule will not apply.

Do you think that my algorithm is correct or am I missing something?

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 t) {
    TreeInfo rootInfo = isFullCompleteTree(t.getRoot());
    return rootInfo.valid;
}

public TreeInfo isFullCompleteTree(Node 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 && leftInfo.valid
            && 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.

StackExchange Code Review Q#88386, answer score: 3