current community

your communities

more stack exchange communities

company blog
Stack Exchange Inbox Reputation and Badges
tour help
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top
up vote 4 down vote favorite

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.rightNode == null){
                return  null;
            }
            runner = runner.rightNode;
        } else {
            return runner;
        }
    }
}

public void insert(int element){
    if(root == null){
        root = new TreeNode(element);
        return;
    }
    TreeNode runner = root;
    while (runner.data != element){
        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<TreeNode> queue = new LinkedList<TreeNode>();
    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<TreeNode> stack = new Stack<TreeNode>();
    if(root == null){
        return;
    }
    TreeNode runner = null;
    stack.add(root);
    while(!stack.empty()){
        runner = stack.peek();
        if(runner.leftNode != null && !runner.leftNode.visited){
            stack.add(runner.leftNode);
            continue;    
        }
        if(runner.rightNode != null && !runner.rightNode.visited){
            stack.add(runner.rightNode);
            continue;
        }
        stack.pop();
        runner.visited = true;
        System.out.println("visited node " + runner.data);
    }
}

public static void preOrderTraversal(TreeNode root){
    if(root == null){
        return;
    }
    System.out.print(root.data + " ");
    preOrderTraversal(root.leftNode);
    preOrderTraversal(root.rightNode);
}

public static void inOrderTraversal(TreeNode root){
    if(root == null){
        return ;
    }
    inOrderTraversal(root.leftNode);
    System.out.print(root.data + " ");
    inOrderTraversal(root.rightNode);
}

private class TreeNode {
    public int data;
    public TreeNode leftNode;
    public TreeNode rightNode;
    public boolean visited;
    TreeNode(int data){
        this.data = data;
    }
}    



@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);
}
assertEquals(tree.get(3).data, 3);
}

}
share|improve this question
    
look into this, well explained: javabypatel.blogspot.in/2015/08/… – Jayesh Oct 6 '15 at 17:17
up vote 3 down vote accepted

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<TreeNode> queue = new LinkedList<TreeNode>();
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.

  1. Change the class declaration to this:

    public class BST<T extends Comparable<T>> {

    Likewise for TreeNode

  2. Replace all comparison operations like x.data < value with x.compareTo(value) < 0, likewise for >

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<TreeNode> queue = new LinkedList<TreeNode>();
    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!)

share|improve this answer
    
You could simplify get even further with while (runner != null) and moving return null after the loop. Maybe not simpler per se, but more what I'm used to seeing. – David Harkness Sep 7 '14 at 16:34
    
Great idea, thanks for that! (updated) – janos♦ Sep 7 '14 at 16:37
    
Thanks for the review, I will incorporate the suggestions – nishant mehta Sep 8 '14 at 19:38
up vote 3 down vote

I try not to cover ground already touched upon by @janos's great answer except to emphasize formatting. You mostly do a good job with the indentation which is clearly the most important factor, but breadthFirstSearch has a while loop whose body isn't indented. Consistent spaces around operators (looks like you do), structural parentheses (if, while, etc), and braces is important, too. As I scan your code, each case of if( and ){ sticks out like a sore thumb and distracts.

Naming two traversal methods Search is misleading. You aren't searching for a specific value. Use traverse or visit instead.

Why are the traversal methods static?

Tree traversal cries out for recursion! So many of your methods would be simpler using recursion instead of loops, stacks, queues, and visited flags (is that flag even necessary with the looping algorithm?).

public static void depthFirstSearch(TreeNode node) {
    if (node == null) {
        return;
    }
    depthFirstSearch(node.left);
    depthFirstSearch(node.right);
    System.out.println("visited node " + runner.data);
}

Ah, reading further I see you used this for preOrderTraversal and inOrderTraversal. Why the difference for post-order?

You can also employ recursion in the other methods such as get and insert. You'll need a helper method to start the recursion, and you can move the recursive methods to TreeNode if you like.

public TreeNode get(int element) {
    return get(root, element);
}

public TreeNode get(TreeNode node, int element) {
    if (node == null) {
        return null;
    }
    else if (node.data > element) {
        return get(node.left, element);
    }
    else if (node.data < element) {
        return get(node.right, element);
    }
    else {
        return node;
    }
}
share|improve this answer
    
I have implemented some methods using iteration while other using recursion for practicing both approaches. Thanks for the review. – nishant mehta Sep 8 '14 at 19:41
up vote 3 down vote

I agree with the reviews by @David Harkness and @janos. I wanted to add a minor point: instead of hard coding your different tree traversal methods to print out the values, you could define those methods to take an argument of type Consumer<T> (where T is the type that replaces the hard code int type). You can then implement a Consumer that just prints out values, but your code could also be used for other things.

share|improve this answer
2  
Another option is to implement each traversal method as an iterator. – David Harkness Sep 7 '14 at 19:27

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.