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

I would like any suggestions and improvements for this code, be it generics or my Node class being completely mutable. Should I make it mutable? Is it good? Why?

package ishan.trees.tree;

class Node implements Comparable<Node> {

    private int data;
    public int getData() {
        return data;
    }

    public void setData(int data) {
        this.data = data;
    }

    public Node getLeftChild() {
        return leftChild;
    }

    public void setLeftChild(Node leftChild) {
        this.leftChild = leftChild;
    }

    public Node getRightChild() {
        return rightChild;
    }

    public void setRightChild(Node rightChild) {
        this.rightChild = rightChild;
    }

    private Node leftChild;
    private Node rightChild;

    public Node(int data,Node leftChild,Node rightChild)
    {
        this.data=data;
        this.leftChild=leftChild;
        this.rightChild=rightChild;

    }

    @Override
    public int compareTo(Node o) {
        if(o.getData() > this.data)
        return -1;

        if(o.getData() < this.data)
            return 1;

        return 0;
    }
}

Tree class

package ishan.trees.tree;

public class Tree {

    private Node root=null;

    public Node getRoot() {
        return root;
    }

    public void insertData(int data)
    {
        Node node=new Node(data,null,null);
        insert(node,this.root);

    }

    private Node insert(Comparable<Node> node,Node root1)
    {
            if(root1==null)
            {

                root1=new Node(((Node)node).getData(),null,null);
                if(this.root==null)
                {
                    this.root=root1;
                }
            }
            else if(node.compareTo(root1) <0)
            {
                root1.setLeftChild(insert(node,root1.getLeftChild()));
            }
            else if(node.compareTo(root1) >0)
            {

                root1.setLeftChild(insert(node,root1.getRightChild()));
            }

     return root1;  
    }
}
share|improve this question
up vote 4 down vote accepted

Three parts to this answer: General Review, Generics, Mutable

General

Style

Java 'style guides' all agree that in Java, the { opening brace should be at the end of the line declaring a code block. So, for example, this code:

public Node(int data,Node leftChild,Node rightChild)
{
    this.data=data;
    this.leftChild=leftChild;
    this.rightChild=rightChild;

}

should be:

public Node(int data,Node leftChild,Node rightChild) {
    this.data=data;
    this.leftChild=leftChild;
    this.rightChild=rightChild;
}

Note, in some places you put the brace on a new line, and in others you do not. Even if you choose to ignore the Java convention, you should at least be consistent.

Variable declarations together

You should move the declarations:

private Node leftChild;
private Node rightChild;

to the top of your class at the same place as your data declaration. All class variables should be declared in one place.

Use the library tools that are available

There are a number of small tricks you can use to make your code simpler. For example, your Node.compareTo() method is:

@Override
public int compareTo(Node o) {
    if(o.getData() > this.data)
    return -1;

    if(o.getData() < this.data)
        return 1;

    return 0;
}

This can be simplified to (Java7 or later):

@Override
public int compareTo(Node o) {
    return Integer.compare(this.data, o.getData());
}

Common constructor

Your Node class has a constructor taking the data, left, and right nodes, but you never supply real values for the left and right nodes, only null. You should probably remove those parameters from the constructor, and just default them to null. Alternatively, have an additional constructor like:

public Node(int data) {
    this(data, null, null);
}

Node permissions

Your node is declared class Node ... which means only classes in the same package as yours can see the Node class, it is not 'public'.

Unfortunately, your Tree class is public: public class Tree and it has the method:

public Node getRoot() {
    return root;
}

That method will not be able to work in a public context at all if the calling class is not in the same package as Node (ishan.trees.tree).

There is no reason to ever expose the Node class to the public. Just remove the getRoot() method.

Recursive insert

The recursive insert mechanism is a little hard for me to follow. Part of the problem is the root1 variable name. I would call it something like levelNode or current. It is not the root.

The following code is too complex:

if(root1==null)
{

    root1=new Node(((Node)node).getData(),null,null);
    if(this.root==null)
    {
        this.root=root1;
    }
}

Note, if root1 is null, we are inserting the new value. There is no reason to make a copy of it (and there's no reason to do the manual cast either (Node)node even if you need to make a copy...)

Doing the setting of the this.root in there as well is.... wrong. Consider the following:

    if(root1==null) {
        return node;
    }

and then, in the calling function:

public void insertData(int data) {
    Node node=new Node(data,null,null);
    Node top = insert(node, this.root);
    if (root == null) {
        root = top;
    }
}

Bug

You do not handle the condition where a duplicate value is inserted, you just ignore it.

Forced Replace

Each level of the recursion, you force the node to change children (normally to the child it was before. I would change that part of the recursion to .. oh, by making the change I would make, it simplifies much of the method....

else if(node.compareTo(root1) < 0) {
    if (root1.getLeftChild() == null) {
        root1.setLeftChild(node);
    } else {
        insert(node, root1.getLeftChild());
    }
} else if(node.compareTo(root1) > 0) {

    if (root1.getRightChild() == null) {
        root1.setRightChild(node);
    } else {
        insert(node, root1.getRightChild());
    }
}

With the above code, there is no need to actually return anything from the method at all, as, other than when the root is null to start with, the method will never be called with a null root1. That means the code can become:

public void insertData(int data) {
    Node node=new Node(data,null,null);
    if (root == null) {
        root = node;
    } else {
        insert(node, root);
    }
}

private void insert(Node node, Node levelNode) {
    if(node.compareTo(levelNode) < 0) {
        if (levelNode.getLeftChild() == null) {
            levelNode.setLeftChild(node);
        } else {
            insert(node, levelNode.getLeftChild());
        }
    } else {

        if (levelNode.getRightChild() == null) {
            levelNode.setRightChild(node);
        } else {
            insert(node, levelNode.getRightChild());
        }
    }
}

Note, that by using just the if/else condition, duplicate values will be handled by inserting to the right.

share|improve this answer

Generics

Since you asked: Sure, generics would be nice. Right now, your Tree would be better named IntBinarySearchTree, as it only accepts integers.

Mutable

Should I make it mutable? Is it good? Why?

No, mutable objects are not good. Very often, they are necessary (because the data changes after the object is created), but if you can make an object immutable, you should do so (because it's easier to handle if you know that it doesn't change).

In this case, I think that it is ok that it is mutable. You could change it, but the resulting code wouldn't be all that pretty, and it would get even worse when you implement more functionality.

Formatting

You are violating a lot of Java style conventions (opening { should be on same line, as should else; whitespace around ==, >, =; etc). If you paste your code into any IDE, it can format it according to conventions.

By convention, the order of elements in a class is: fields, constructor, methods. I would go with this order, so readers can easily find them.

private Node class

As your Node class is never used on its own, and never outside of the Tree class, it should be a private class inside Tree.

Node constructor

It's always a bit ugly to pass null to a constructor. I would create an additional constructor that only takes data as input.

compareTo

Your compareto method can be replaced with return this.data - o.getData();. It's a bit less readable, but it is how it's done most of the time, so readers will be used to it. You might also want to check if the passed node is not null, and if it is handle it accordingly.

insert

You should move the code for inserting the first root node to insertData. It just complicates insert.

I would also rename root1 to currentRoot.

And I would write a toString method for the tree to test it. Right now, your code doesn't seem quite right (you are doing root1.setLeftChild in both cases).

share|improve this answer
2  
Got my +1, but note that return this.data - o.getData(); is buggy, because if the values are more than Integer.MAX_VALUE different, the subtraction will overflow and cause a wrong result. – rolfl Oct 10 '14 at 12:57

Postpone the creation on the Node to be inserted. Under other circumstances (for instance not inserting when already present) this makes even more sense.

I have made the current Node the first parameter too.

Futhermore setters and getters on Node are IMHO a bit overdone. I think here even leading to copy errors because of verbosity.

The Node constructor would only need data as parameter.

public void insertData(int data) {
    root = insert(root, data);
}

/**
 * @param subtree the current Node in the tree.
 * @param data comparable information.
 * @return the possibly changed subtree.
 */
private Node insert(Node subtree, int data) {
    if (subtree == null) {
        return new Node(data, null, null);
    }
    if (data < subtree.data) { // <= ?
        subtree.left = insert(subtree.left, data);
    } else if (data > subtree.data) {
        subtree.right = insert(subtree.right, data);
    }
    return subtree;  
}

The insert must decide what to do with already present data. State it in the javadoc.

share|improve this answer

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.