Algorithm that checks if a tree is full and complete

Question

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

Answer 1

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

public TreeInfo isFullCompleteTree(Node<Integer> 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.

Answer 2

I suppose the code works and will just share my thoughts about it (how it can be improved), so don't expect any code :)

In case the code does not work (I didn't see any piece of code where you checked the depth of the leafs) I would suggest to post the question in stack overflow.

That being said, I think the TreeInfo class is not necessary, if you are using it only for this method. The idea you had is good but the implementation does too much.

What you need to know for each node are the following:

1. Depth,
2. If it is a leaf.

With this information (and the depth of the tree) you can calculate if the tree is full and complete.