Create a complete binary tree

Question

Write a program to create a complete binary tree, which includes an addItem method such that an individual element can be inserted into the tree to maintain the property that tree is complete.

I'm looking for code review, optimizations and best practices. This code is attributed to GeeksForGeeks.

I am also not sure how to unit test this code. More specifically, how to generate the input to equals function. The tree I would compare would be using the same addItem method which is destroying the whole purpose of unit testing.

public class CreateCompleteBinaryTree<T> {

    private TreeNode<T> root;

    public CreateCompleteBinaryTree(List<T> items) {
        for (T item : items) {
            addItem(item);
        }
    }

    private static class TreeNode<T> {
        private TreeNode<T> left;
        private T item;
        private TreeNode<T> right;

        TreeNode(T item) {
            this.item = item;
        }
    }

    /**
     * Adds item, such the tree is a complete binary tree.
     * 
     * @param item the item to be added.
     */
    public void addItem(T item) {

        System.out.println(item);

        if (root == null) {
            root = new TreeNode<T>(item);
            return;
        }

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

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

            if (currNode.left == null) {
                currNode.left = new TreeNode<T>(item);
                return;
            }

            if (currNode.right == null) {
                currNode.right = new TreeNode<T>(item);
                return;
            }

            queue.add(currNode.left);
            queue.add(currNode.right);
        }
    }

    @Override
    public int hashCode() {
        final int prime = 31;
        int result = 1;
        result = prime * result + ((root == null) ? 0 : root.hashCode());
        return result;
    }

    @Override
    public boolean equals(Object obj) {
        if (this == obj)
            return true;
        if (obj == null)
            return false;
        if (getClass() != obj.getClass())
            return false;
        CreateCompleteBinaryTree other = (CreateCompleteBinaryTree) obj;
        return equal(root, other.root);
    }


    private static boolean equal(TreeNode node1, TreeNode node2) {

        if (node1 == null && node2 == null) return true;
        if (node1 == null || node2 == null) return false;
        if (node1.item != node2.item) {
            System.out.println("---: " + node1.item + " : " + node2.item);
            return false;
        }

        return equal(node1.left, node2.left) && equal(node1.right, node2.right);
    }
}

Answer 1

There are two major issues I see with your implementation, one functional, and one performance.

You have implemented the equals() method and, additionally, you have implemented the hashCode() method too. It is good that you are implementing them both, but, they are broken.

The hashCode() method only calculates the hashCode of the root node (if any), and it does not calculate it off the value in the node, but off the node itself.

@Override
public int hashCode() {
    final int prime = 31;
    int result = 1;
    result = prime * result + ((root == null) ? 0 : root.hashCode());
    return result;
}

You do not override the hashCode of TreeNode, so the result is just a somewhat unique number, and thus, even if you have two trees with the same value at the root, they will have different hashCode values. If you override equals, you have to override hashCode, but, if you override hashCode, do it properly!

The Performance issue relates to the core addItem method. Your method is an \$O(n)\$ operation, scanning almost the entire tree, to get to the last item added.

A better algorithm would be to maintain a stack of the path to the most recently added node's parent. This would be maintained at the same time as the root node.... consider:

Deque<TreeNode<T>> insertPoint = new LinkedList<>();
TreeNode root = null;

Then, when you add an item:

/**
 * Adds item, such the tree is a complete binary tree.
 * 
 * @param item the item to be added.
 */
public void addItem(T item) {

    if (root == null) {
        root = new TreeNode<T>(item);
        return;
    }

    if (!insertedAt.isEmpty() && insertedAt.peek().right != null) {
        TreeNode<T> kid = insertedAt.pop();
        while (!insertedAt.isEmpty() && kid == insertedAt.peek().right) {
            kid = insertedAt.pop();
        }
        if (!insertedAt.isEmpty()) {
            kid = insertedAt.peek();
            kid = kid.right;
            insertedAt.push(kid);
            while (kid.left != null) {
                kid = kid.left;
                insertedAt.push(kid);
            }
        }
    }

    if (insertedAt.isEmpty()) {
        // filled the leaf row, go down the left edge again.
        TreeNode<T> node = root;
        while (node != null) {
            insertedAt.push(node);
            node = node.left;
        }
    }

    TreeNode<T> node = insertedAt.peek();
    TreeNode<T> toadd = new TreeNode<>(item);
    if (node.left == null) {
        node.left = toadd;
    } else {
        node.right = toadd;
    }

}

What the above code does, is keep the most recently added-to node at the top of the stack. Then, if the node can still be added to, it fills it.

If the node is now full, it goes back up the tree, looking for the next insertion point, which may nto exist on this level. If it does not then it goes all the way down the left edge and starts a new level....

This means that, for many inserts (half of them?), the performance is \$O(1)\$ and for the worst case, when you have just completed a level of the tree, and you have to start over again at the left, it requires one walk up the right edge, and back down the left edge, in an \$O(\log{n})\$ operation.

So, this brings the process from a \$O(n)\$ operation with \$O(\log{n})\$ space complexity, to a worst-case \$O(\log{n})\$ operation with \$O(\log{n})\$ space as well.