Binary search tree with tree traversal

Although there are several implementations of binary search tree, I have made my own implementation for practice. The following code does the followoing operation

• Create a binary tree
• search through a binary tree
• inorder traversal
• preorder traversal
• breadth first traversal
• depth first traversal(post order)

Please suggest improvements or possible short comming in the code

```
import static org.junit.Assert.assertEquals;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
import org.junit.Test;

public class BST {
public TreeNode root = null;

public TreeNode get(int element){
if(root == null){
return null;
}
TreeNode runner = root;
while (true){
if(runner.data > element){
if(runner.leftNode == null){
return null;
}
runner = runner.leftNode;
} else if(runner.data element){
if(runner.leftNode == null){
runner.leftNode = new TreeNode(element);
return;
}
runner = runner.leftNode;
} else {
if(runner.rightNode == null){
runner.rightNode = new TreeNode(element);
return;
}
runner = runner.rightNode;
}
}
}

public static void breathFirstSearch(TreeNode root){
Queue queue = new LinkedList();
queue.add(root);
TreeNode runner = root;
while(!queue.isEmpty()){
runner = (TreeNode)queue.remove();
if(runner.leftNode != null){
queue.add(runner.leftNode);
}
if(runner.rightNode != null){
queue.add(runner.rightNode);
}
System.out.println("visited node " + runner.data);
}
}

public static void depthFirstSearch(TreeNode root){
Stack stack = new Stack();
if(root == null){
return;
}
TreeNode runner = null;
stack.add(root);
while(!stack.empty()){
runner = stack.peek();
if(runner.leftNode != null && !runn

Simplify get

You can simplify the get method like this:

public TreeNode get(int element) {
    TreeNode runner = root;
    while (runner != null) {
        if (runner.data > element) {
            runner = runner.leftNode;
        } else if (runner.data < element) {
            runner = runner.rightNode;
        } else {
            return runner;
        }
    }
    return null;
}

(Thanks @david-harkness for pointing out the extra shortcut!)

Breadth-first search

It's called breadth-first, not "breath-first".

Also, this initialization is pointless, as you overwrite the value of runner immediately in the loop:

Queue queue = new LinkedList();
queue.add(root);
TreeNode runner = root;
while (!queue.isEmpty()) {
    runner = (TreeNode) queue.remove();

And, the cast is also pointless, because the Queue is correctly declared with TreeNode type.

Depth-first search

The depthFirstSearch method will set all node.visited = true, so you won't be able to call it twice. Actually it's really bad to have side effects like this. It would be better if TreeNode didn't have the visited field at all. It's polluting the class with data only used by one specific purpose, the depth-first search. It doesn't belong there. You could track what was visited using a Set, used only in depthFirstSearch.

TreeNode

I would rename leftNode to left and rightNode to right. It's simpler and everybody understands what they are.

Since you never need to change data, it can be final.

The current implementation is limited to int values. It would be better if the BST could store anything comparable.

-
Change the class declaration to this:

public class BST> {

Likewise for TreeNode

-
Replace all comparison operations like x.data

Unit testing

Your basic test could easily become more useful (and less basic) if you do a get not only for one random element, but for all elements you inserted, since you have the array of values ready anyway:

@Test
public void basicTest() {
    BST tree = new BST();
    int[] data = {9, 5, 3, 1, 4, 8, 15, 11, 21, 20, 29};
    for (int i : data) {
        tree.insert(i);
    }
    for (int i : data) {
        assertEquals(i, tree.get(i).data);
    }
}

A single test case named basicTest is not going to make this class "properly tested". At the very least you could add a few more test cases that are obviously necessary when talking about a binary search tree.

For example, what happens if you try to get non-existent elements?

@Test
public void testNoSuchElement() {
    BST tree = new BST();
    assertNull(tree.get(3));
    assertNull(tree.get(31));
}

The BST should not allow duplicate values:

@Test
public void testNoDuplicateVaues() {
    BST tree = new BST();
    int val = 3;
    tree.insert(val);
    tree.insert(val);
    tree.insert(val);
    assertEquals(1, tree.size());
}

Of course this requires a .size method, so implement one, and a test case with it too:

public int size() {
    int count = 0;
    Queue queue = new LinkedList();
    queue.add(root);
    TreeNode runner;
    while (!queue.isEmpty()) {
        runner = queue.remove();
        if (runner != null) {
            ++count;
            queue.add(runner.leftNode);
            queue.add(runner.rightNode);
        }
    }
    return count;
}

@Test
public void testSize() {
    assertEquals(0, new BST().size());
    BST tree = new BST();
    int[] data = {9, 5, 3, 1, 4, 8, 15, 11, 21, 20, 29};
    for (int i : data) {
        tree.insert(i);
    }
    assertEquals(data.length, tree.size());
}

Formatting

The formatting is messy:

• the indentation is broken in breathFirstSearch and in basicTest

• you should put a space before and after parentheses, for example:

• while(!stack.empty()){ should be formatted as while (!stack.empty()) {

• if(root == null){ should be formatted as if (root == null) {

Basically, use your IDE to format code correctly. It also makes it easier to review. (For yourself too!)

StackExchange Code Review Q#62192, answer score: 3