Java pass by value with recursion
Below is a simple implementation of a binary search tree using java. However, the code always prints "BST empty !!". despite inserting elements. Where am I going wrong? I suspect I was wrong with the recursion. Any help is appreciated.
public class BinarySearchTree {
NODE root;
BinarySearchTree(){
root = null;
}
void insert(NODE nodeptr,int key){
if(root == null){
nodeptr = new NODE(key);
return;
}
if(nodeptr == null){
nodeptr = new NODE(key);
return;
}
if(key <= nodeptr.data){
insert(nodeptr.left,key);
}
else{
insert(nodeptr.right,key);
}
}
void inorder(NODE nodeptr){
if(nodeptr == null){
System.out.println("BST empty!!");
return;
}
inorder(nodeptr.left);
System.out.println(nodeptr.data + " ");
inorder(nodeptr.right);
}
/*driver program*/
public static void main(String args[]){
int[] a = {20,30,40,24,39};
BinarySearchTree bst = new BinarySearchTree();
for (int i: a){
bst.insert(bst.root,i);
}
bst.inorder(bst.root);
}
}
class NODE{
int data;
NODE left,right;
NODE(int data){
this.data = data;
left = null;
right = null;
}
}
source to share
Your method insert
never assigns a value to the root, so it stays at zero.
If I understand your code, your insert should look like this:
void insert(NODE nodeptr,int key){
if(root == null){
root = new NODE(key);
return;
}
if(nodeptr == null){
insert (root, key);
return;
}
if(key <= nodeptr.data){
if (nodeptr.left != null)
insert(nodeptr.left,key);
else
nodeptr.left = new NODE(key);
}
else{
if (nodeptr.right != null)
insert(nodeptr.right,key);
else
nodeptr.right = new NODE(key);
}
}
- If the value
root
is null, ignore the traversednodeptr
and putkey
in the root of the tree. - If it
nodeptr
is null, try inserting a new key starting at the root of the tree. - otherwise, as soon as you find zero
nodeptr.left
ornodeptr.right
, you should put a new one herekey
, because if you make another recursive call, you will pass null Node to it, and the recursion will never end.
source to share
Expanding on Erance's answer, you can change it to:
public void insert(int key){
if(root == null){
root = new NODE(key);
return;
}
insert(root,key)
}
private void insert(NODE nodeptr,int key){
if(key <= nodeptr.data){
if(nodeptr.left == null){
nodeptr.left = new NODE(key)
}
else {
insert(nodeptr.left,key);
}
}
else{
if(nodeptr.right == null){
nodeptr.right = new NODE(key)
}
else {
insert(nodeptr.right,key);
}
}
}
Edit: Since he added his own code, it is now a matter of which style you like best. One method or two methods, of which public has only one parameter.
source to share
I wanted my insert method to be something like this. Got this to finally work. Thank you all for your precious time.
NODE insert(NODE nodeptr,int key){
if(nodeptr == null){
nodeptr = new NODE(key);
}
else if(key <= nodeptr.data){
nodeptr.left = insert(nodeptr.left,key);
}
else{
nodeptr.right = insert(nodeptr.right,key);
}
return nodeptr;
}
I would call the insert method from main like this:
bst.root = bst.insert(bst.root,i);
source to share