• 1

• 22.5k
• 5
• 68
• 144

• 8.5k
• 29
• 93
• 162

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

public class CompleteBinaryTreeDetection<T> {
 
 private TreeNode<T> 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<T> items) {
 create(items);
 }
 private void create (List<T> items) {
 root = new TreeNode<T>(null, items.get(0), null);
 
 final Queue<TreeNode<T>> queue = new LinkedList<TreeNode<T>>();
 queue.add(root);
 final int half = items.size() / 2;
 
 for (int i = 0; i < half; i++) {
 if (items.get(i) != null) {
 final TreeNode<T> current = queue.poll();
 final int left = 2 * i + 1;
 final int right = 2 * i + 2;
 if (items.get(left) != null) {
 current.left = new TreeNode<T>(null, items.get(left), null);
 queue.add(current.left);
 }
 if (right < items.size() && items.get(right) != null) {
 current.right = new TreeNode<T>(null, items.get(right), null);
 queue.add(current.right);
 }
 }
 }
 }
 
 
 /**
 * TreeNode
 */
 private static class TreeNode<T> {
 TreeNode<T> left;
 T item;
 TreeNode<T> right;
 
 public TreeNode(TreeNode<T> left, T item, TreeNode<T> 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;
 }
 }
 
 private Data check(TreeNode<T> node) {
 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);
 }
 }
}
import static org.junit.Assert.assertFalse;
import static org.junit.Assert.assertTrue;
import java.util.Arrays;
import org.junit.Test;
public class CompleteBinaryTreeDetectionTest {
 
 @Test
 public void test1() {
 /**
 * 1
 * 2 3 
 * 4 n n n
 */
 CompleteBinaryTreeDetection<Integer> createTree1 = new CompleteBinaryTreeDetection<Integer>(Arrays.asList(1, 2, 3, 4, null, null, null));
 assertTrue(createTree1.isComplete());
 }
 
 @Test
 public void test2() {
 /**
 * 1
 * 2 3 
 * 4 5 n n
 */
 CompleteBinaryTreeDetection<Integer> createTree2 = new CompleteBinaryTreeDetection<Integer>(Arrays.asList(1, 2, 3, 4, 5, null, null));
 assertTrue(createTree2.isComplete());
 }
 
 @Test
 public void test3() {
 /**
 * 1
 * 2 3 
 * 4 5 6 n
 */
 CompleteBinaryTreeDetection<Integer> createTree3 = new CompleteBinaryTreeDetection<Integer>(Arrays.asList(1, 2, 3, 4, 5, 6, null));
 assertTrue(createTree3.isComplete());
 }
 
 @Test
 public void test4() {
 /**
 * 1
 * 2 3 
 * 4 5 6 7
 */
 CompleteBinaryTreeDetection<Integer> createTree4 = new CompleteBinaryTreeDetection<Integer>(Arrays.asList(1, 2, 3, 4, 5, 6, 7));
 assertTrue(createTree4.isComplete());
 }
 
 @Test
 public void test5() {
 /**
 * 1
 * 2 3 
 * 4 5 6 7
 * 8 
 */
 CompleteBinaryTreeDetection<Integer> createTree5 = new CompleteBinaryTreeDetection<Integer>(Arrays.asList(1, 2, 3, 4, 5, 6, 7, null, 8));
 assertFalse(createTree5.isComplete());
 }
 
 @Test
 public void test6() {
 /**
 * 1
 * 2 3 
 * 4 5 6 7
 * 8 9 
 */
 CompleteBinaryTreeDetection<Integer> createTree6 = new CompleteBinaryTreeDetection<Integer>(Arrays.asList(1, 2, 3, 4, 5, 6, 7, null, 8, 9));
 assertFalse(createTree6.isComplete());
 }
 
 @Test
 public void test7() {
 /**
 * 1
 * 2 3 
 * 4 5 6 7
 * 8 
 */
 CompleteBinaryTreeDetection<Integer> createTree7 = new CompleteBinaryTreeDetection<Integer>(Arrays.asList(1, 2, 3, 4, 5, 6, 7, null, null, null, null, 8));
 assertFalse(createTree7.isComplete());
 }
 
 @Test
 public void test8() {
 /**
 * 1
 * 
 */
 CompleteBinaryTreeDetection<Integer> createTree8 = new CompleteBinaryTreeDetection<Integer>(Arrays.asList(1));
 assertTrue(createTree8.isComplete());
 }
}