Detect a complete binary tree

Follow-up question: Detect if a tree is complete binary tree

Detect if a tree is complete binary tree or not. Looking for code review, optimizations and best practices.

```
public class CompleteBinaryTreeDetection {

private TreeNode root;

/**
* Constructs a binary tree in order of elements in an array.
* After the number of nodes in the level have maxed, the next
* element in the array would be a child of leftmost node.
*/
public CompleteBinaryTreeDetection(List items) {
create(items);
}

private void create (List items) {
root = new TreeNode(null, items.get(0), null);

final Queue> queue = new LinkedList>();
queue.add(root);

final int half = items.size() / 2;

for (int i = 0; i current = queue.poll();
final int left = 2 * i + 1;
final int right = 2 * i + 2;

if (items.get(left) != null) {
current.left = new TreeNode(null, items.get(left), null);
queue.add(current.left);
}
if (right (null, items.get(right), null);
queue.add(current.right);
}
}
}
}

/**
* TreeNode
*/
private static class TreeNode {
TreeNode left;
T item;
TreeNode right;

public TreeNode(TreeNode left, T item, TreeNode right) {
this.left = left;
this.item = item;
this.right = right;
}
}

/**
* Returns true if binary tree is complete
*
* @return true if tree is complete else false.
*/
public boolean isComplete() {
if (root == null) {
throw new NoSuchElementException();
}
return check(root).b;
}

private static class Data {
boolean b;
int height;

Data (boolean b, int height ) {
this.b = b;
this.height = height;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.NoSuchElementException;
import java.util.Queue;

public class CompleteBinaryTreeDetection {

why is this not final?

private TreeNode root;

    /**
     * Constructs a binary tree in order of elements in an array.
     * After the number of nodes in the level have maxed, the next
     * element in the array would be a child of leftmost node.
     */
    public CompleteBinaryTreeDetection(List items) {

why have you moved the creation logic to a separate function with a horrible name?

create(items);
    }

    private void create (List items) {

why not use java7 diamond operator?

root = new TreeNode(null, items.get(0), null);

though possible, it is not really necessary to apply final to local variables

final Queue> queue = new LinkedList>();
        queue.add(root);

        final int half = items.size() / 2;

        for (int i = 0; i  current = queue.poll();
                final int left = 2 * i + 1;
                final int right = 2 * i + 2;

                if (items.get(left) != null) {
                    current.left = new TreeNode(null, items.get(left), null);
                    queue.add(current.left);
                }
                if (right (null, items.get(right), null);
                    queue.add(current.right);
                }
            }
        }
    }

extremely helpful javadoc :)

/**
     * TreeNode
     */
    private static class TreeNode {
        TreeNode left;
        T item;
        TreeNode right;

        public TreeNode(TreeNode left, T item, TreeNode right) {
            this.left = left;
            this.item = item;
            this.right = right;
        }
    }

it should really be a static method

/**
     * Returns true if binary tree is complete
     *
     * @return true if tree is complete else false.
     */
    public  boolean isComplete() {

is it possible? and if it is, IllegalStateException is more appropriate here

if (root == null) {
            throw new NoSuchElementException();
        }
        return check(root).b;
    }

Hello, the guy reading this code. This is a class called "Data" with a member variable "b". Can you guess what it does?

private static class Data {
        boolean b;
        int height;

you have a few whitespaces hanging around the place. please stick to a coherent style.

Data (boolean b, int height ) {
            this.b = b;
            this.height = height;
        }
    }

    private Data check(TreeNode node) {

why -1? shouldn't it be 0?

if (node == null) return new Data(true, -1);

        Data left = check (node.left);
        Data right = check (node.right);

        if (!left.b) return left;
        if (!right.b) return right;

        // defn of complete tree
        if (left.height == right.height + 1 || left.height == right.height) {
            return new Data(true, left.height + 1);
        } else {
            return new Data(false, left.height + 1);
        }
    }
}

But all that was not important. Let's look at definition of a complete binary tree from wikipedia: "A complete binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible. A tree is called an almost complete binary tree or nearly complete binary tree if the exception holds, i.e. the last level is not completely filled. This type of tree is used as a specialized data structure called a heap."

Here's a test that your program fails:

@Test
public void oops() {
    /**
     *         1
     *       2   3
     *     4  n  5 n
     */
    CompleteBinaryTreeDetection createTree1 = new CompleteBinaryTreeDetection(
            Arrays.asList(1, 2, 3, 4, null, 5, null));
    assertFalse(createTree1.isComplete());
}

I suggest rewriting the algo as a BFS, holding two layers of the tree in the memory at once. Checking for completeness should be really easy then.

StackExchange Code Review Q#54970, answer score: 5