Complete Binary Tree

Check a binary tree is completed or not. A complete binary tree is a binary tree that every level is completed filled except the deepest level. In the deepest level, all nodes must be as left as possible.

Solution:

There are only two scenario for a complete binary tree:

• when left.depth == right.depth, left subtree is full and right subtree is full or complete
• when left.depth == right.depth + 1, left subtree is complete and right subtree is full

Code:

class ResultType {
    int height;
    boolean isComplete;
    boolean isFull;
    public ResultType(int inHeight, boolean inComplete, boolean inFull) {
        height = inHeight;
        isComplete = inComplete;
        isFull = inFull;
    }
}

public class Solution {

    public boolean isComplete(TreeNode root) {
        return helper(root).isComplete;
    }

    private ResultType helper(TreeNode root) {
        if (root == null) {
            return new ResultType(0, true, true);
        }
        ResultType left = helper(root.left);
        ResultType right = helper(root.right);

        if (left.height == right.height && left.isFull) {
            return new ResultType(left.height + 1, right.isComplete, right.isFull);
        }
        if (left.height == right.height + 1 && left.isComplete) {
            return new ResultType(left.height + 1, right.isFull, false);
        }

        return new ResultType(-1, false, false);
    }
}