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.