4
\$\begingroup\$

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());
    }
}
\$\endgroup\$
5
\$\begingroup\$
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.NoSuchElementException;
import java.util.Queue;

public class CompleteBinaryTreeDetection<T> {

why is this not final?

    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) {

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

        create(items);
    }

    private void create (List<T> items) {

why not use java7 diamond operator?

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

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

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

extremely helpful javadoc :)

    /**
     * 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;
        }
    }

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<T> 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<Integer> createTree1 = new CompleteBinaryTreeDetection<Integer>(
            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.

\$\endgroup\$
  • 1
    \$\begingroup\$ Why should isComplete be a static method? Being complete is a property of the tree instance, so it makes sense to me to keep it an instance method. \$\endgroup\$ – svick Jun 27 '14 at 13:54
  • \$\begingroup\$ it's okay for isComplete to be a method of a Tree instance. But a member of CompleteBinaryTreeDetection ? \$\endgroup\$ – abra Jun 28 '14 at 15:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.