2
\$\begingroup\$

Detect if tree is complete binary tree. This question is improvement over previously asked here. Looking for code-review, optimizations and best practices.

Verifying both space and time complexity to be O(n), where n is number of nodes.

public final 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();
                int left = 2 * i + 1;
                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);
                }
            }
        }
    }

    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();
        }
        final Queue<TreeNode<T>> queue = new LinkedList<TreeNode<T>>();
        queue.add(root);

        boolean incompleteDetected = false;

        while (!queue.isEmpty()) {
            TreeNode<T> node = queue.poll();

            if (node.left != null) { 
                if (incompleteDetected) return false;
                queue.add(node.left);
            } else {
                incompleteDetected = true;
            }

            if (node.right != null) {
                if (incompleteDetected) return false;
                queue.add(node.right);
            } else {
                incompleteDetected = true;
            }
        }
        return true;
    }
}


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

    @Test
    public void test9() {
        /**
         *         1
         *       2   3  
         *     4  5   6  7
         *   8       9       
         */
         CompleteBinaryTreeDetection<Integer> createTree9 = new CompleteBinaryTreeDetection<Integer>(Arrays.asList(1, 2, 3, 4, 5, 6, 7, 8, null, null, null, 9));
         assertFalse(createTree9.isComplete());
    }
}
\$\endgroup\$
5
\$\begingroup\$

I'm not even going to look at cosmetic issues like variable names (which look reasonably ok anyway).

  1. I fail to see why the constructor consists of just one line, which is a call to a private method. Eliminate the create method and roll it's code into the constructor.

  2. Using a queue to keep track of where you are in the tree is kind of clever, except that it's clever at the expense of readability and complexity. The best solution (defined by standard practices) for any tree algorithm is almost always recursive.

    The tricky part is knowing how to define the algorithm in recursive terms. Here are some example algorithms:

    a. When constructing a node, pass the node number. The root is zero. The left node of node n is 2 * n + 1 and the right node is 2 * n + 2. Don't create the node if the value in items for that node number is null.

    b. When checking for completeness, calculate the height on the left side and on the right side.

    1. If the left side is full (height h), then the right side must be complete with height h or full with height h - 1

    2. If the left side is not full, it must be complete and have height of h. The right side must be full with height h - 1.

\$\endgroup\$
  • \$\begingroup\$ "I fail to see why the constructor consists of just one line, which is a call to a private method. Eliminate the create method and roll it's code into the constructor." +1. I absolutely hate that pattern. \$\endgroup\$ – async Sep 6 '14 at 23:15
2
\$\begingroup\$

No empty tree?

The code forbids creating an empty tree:

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

This method, called by the constructor, will throw an exception for an empty list. Empty lists have legitimate use cases, that's why empty lists, sets, maps exist in the language. It will be good and easy to allow an empty tree.

Add a convenience constructor

Since you seem to create tree nodes typically with no children, it would be good to add a convenience constructor:

public TreeNode(T item) {
    this(null, item, null);
}

Also, item is not a great name for the value of the node. data is a common choice, or value could be good too. And since you never change it, the field can be final.

A small note about performance

A note about performance when creating the tree: you are using the random access method .get on a List. This is fine when the underlying implementation of the received List supports efficient random access, like in an ArrayList. If your method is called with a LinkedList, the multiple .get calls will be inefficient. A workaround for that case can be using a local ArrayList for populating the tree, something like this:

List<T> items = new ArrayList<>(origItems.size());
items.addAll(origItems);

Validation

I don't really agree with this handling of an empty tree:

public boolean isComplete() {
  if (root == null) {
      throw new NoSuchElementException();
  }

I think it would make sense to consider an empty tree complete. Or not, if that's what you prefer. Either way, NoSuchElementException is not appropriate here. NoSuchElementException is used when you try to get an element that doesn't make sense, for example the maximum value or an empty collection.

Unit testing

I get it that you probably think that each test case is just another simple example, so numbering is fine. That's partly true, and numbering as opposed to descriptive naming can be acceptable sometimes. But you can at least divide your test cases into 2 groups: confirm complete vs confirm non-complete. So this kind of naming would have been better:

  • testCompleteExample1
  • testCompleteExample2
  • ...
  • testNonCompleteExample1
  • testNonCompleteExample2
  • ...

So that when something fails, I get a simple clue immediately about the kind of failure.

Also, making the numbers correspond to the number of nodes in the tree can be a useful clue too.

\$\endgroup\$
1
\$\begingroup\$

I'd maybe go for recursion for simplicity, but beware of the StackOverflowException. It can hardly happen for a complete tree as a sufficiently deep such tree wouldn't fit in memory, but an incomplete could blow the recursion easily.

I don't really understand your algorithm, but it's smart. I'd go for a stack instead of a queue as a stack is like recursion, and therefore easier to comprehend.

I'd look for nodes with only one child and also check if all leaves have the same depth. This sounds trivial, doesn't it?

\$\endgroup\$
0
\$\begingroup\$

The major problem with your solution is that you need an extra O(N) memory for your queue. A recursive solution would only require an expected O(log N) memory for the stack (even though it is still O(N) worst case).

PS: actually, if you expect very unbalanced trees, scanning the tree breadth-first with a queue can be an advantage. But for random trees I think the expected queue length will still grow like O(N).

\$\endgroup\$

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.