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<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());
}
}
