Creating a binary search tree

Question

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

Answer 1

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.left == null) {
                node.left = new TreeNode(null, item, null);
                break;
            }
            node = node.left;
        } else 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.left == null) {
            node.left = new TreeNode(null, item, null);
        } else {
            add(node.left, item);
        }
    } else 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);
    }
}

Answer 2

root is created if and only if you add an element. From the BST I know, the root always exists, even if the tree contains no elements.

Also, the name is confusing. Is it a 'BST creator'? Then the name is ok, but some 'BST' itself should be accessible.

Is it just a BST? Then the name should be changed to 'BinarySearchTree' and you should provide more methods to acually be able to use the BST.

Answer 3

Correctness:

One thing many BST's need to define is the behavior when an item already exists and you attempt to add it again. Usually this means that you will locate the position of the existing item and then do nothing; I personally recommend replacing it (more useful with generics; doesn't make sense with integers). In your case, I think you add it again - this is probably not what is desired.

Performance:

Like most simple BSTs, your class ends up being a limited linked list if the input data is already sorted. Consider learning about AVL or Red-Black trees to find a way to auto-balance your BST.

Usefulness:

Currently you only have methods to add to the structure but it doesn't have helpful methods like contains or traverse/visit.

Consider moving your constructor CreateBinarySearchTree(int[] a) to a more general add(int[] a); this would allow you to add an array of values at some other point besides construction (such as adding two arrays to the tree to use it as a way to identify unique values). Some people would also argue that such methods are inherently useless. I suggest evaluating if adding an array is more helpful than just iterating across the array in the calling code.