Creating a binary search tree

I want you to pick my code apart and give me some feedback on how I could make it better or simpler. Although, agree that generics should be used, instead of integers, let's punt on generics as a review for now.

public class CreateBinarySearchTree {

    private TreeNode root;

    public CreateBinarySearchTree() {
    }

    /**
     * Will create a BST imperative on order of elements in the array
     */
    public CreateBinarySearchTree(int[] a) {
        this();
        for (int i : a) {
            add(i);
        }
    }

    private static class TreeNode {
        TreeNode left;
        int item;
        TreeNode right;

        TreeNode(TreeNode left, int item, TreeNode right) {
            this.left = left;
            this.right = right;
            this.item = item; 
        }
    }

    public void add(int item) {
        if (root == null) {
            root = new TreeNode(null, item, null);
            return;
        }

        TreeNode node = root;
        while (true) {
            if (item < node.item) {
                if (node.left == null) {
                    node.left = new TreeNode(null, item, null);
                    break;
                }
                node = node.left;
            } else {
                if (node.right == null) {
                    node.right = new TreeNode(null, item, null);
                    break;
                }
                node = node.right;
            }
        }
    }
}

This class is too basic to be useful. You can only add nodes to it, but you don't provide a way to access those nodes. As such this is something incomplete.

Make it testable

At the minimum, make it testable. For example by implementing a toString method:

@Override
public String toString() {
    return toString(root);
}

private String toString(TreeNode node) {
    if (node == null) {
        return null;
    }
    return "[" + toString(node.left) + "," + node.item + "," + toString(node.right) + "]";
}

Now we can write some tests to verify it's actually working:

@Test
public void test345() {
    CreateBinarySearchTree tree = new CreateBinarySearchTree();
    tree.add(3);
    tree.add(4);
    tree.add(5);
    assertEquals("[null,3,[null,4,[null,5,null]]]", tree.toString());
}

@Test
public void test453() {
    CreateBinarySearchTree tree = new CreateBinarySearchTree();
    tree.add(4);
    tree.add(5);
    tree.add(3);
    assertEquals("[[null,3,null],4,[null,5,null]]", tree.toString());
}

NOT a Binary Search Tree

The implementation violates a requirement of a Binary Search Tree: it will add duplicate elements. Let's expose this bug by adding a unit test:

@Test
public void testNoDups() {
    CreateBinarySearchTree tree = new CreateBinarySearchTree();
    tree.add(4, 4);
    tree.add(4);
    assertEquals("[null,4,null]", tree.toString());
}

Easy enough to fix, by adding an else in the main loop:

while (true) {
        if (item  node.item) {
            if (node.right == null) {
                node.right = new TreeNode(null, item, null);
                break;
            }
            node = node.right;
        } else {
            break;
        }
    }

Recursive add

Instead of a while loop, it would be more elegant to implement adding a node using recursion:

public void add(int item) {
    if (root == null) {
        root = new TreeNode(null, item, null);
    } else {
        add(root, item);
    }
}

public void add(TreeNode node, int item) {
    if (item  node.item) {
        if (node.right == null) {
            node.right = new TreeNode(null, item, null);
        } else {
            add(node.right, item);
        }
    }
}

Minor things

public CreateBinarySearchTree() {}

public CreateBinarySearchTree(int[] a) {
    this();
    for (int i : a) {
        add(i);
    }
}

The constructor that takes an array calls this(), but since that other constructor does nothing, this is pointless. The variable names a and i are poor, it would be better to rename them to arr or items, and item, respectively.

As others have pointed out, it would make sense to move the adding logic outside of the constructor. In fact, how about removing all the constructors, and using this new method instead to add elements:

public void add(int... items) {
    for (int item : items) {
        add(item);
    }
}

StackExchange Code Review Q#31994, answer score: 14