CODEWITHSUNDEEP
javabinary-tree
varun jana
varun jana

Reputation: 13

Cannot seem to insert into Binary search tree

When I implement insert and print in binary search tree. it only prints out the first root node. Please help why? Basic implementation of binary search trees, starting out in learning them and moving to more advanced stuff with them, but stumbling at the first step. It looks like it is not adding the nodes to the root node.

class bstrees{
class Node
 {
     int data;
     Node left;
     Node right;
     public Node(int data)
     {
         this.data=data;
         this.left=null;    
         this.right=null;
     }
 }
Node root;
bstrees(){root=null;}

public void insert(int data){
    root=insert_node(root,data);
}
public Node insert_node(Node r,int n){
    if(r==null){
        Node n1=new Node(n);
        //root=n1;
        return n1 ;
    }
    else if(root.data<=n){
        insert_node(root.right,n);
    }
    else{
        insert_node(root.left,n);
    }
    return r;
}
public void print_t(){
    print_t(root);
}
private void print_t(Node r){
    //System.out.println(r);
    if(r!=null){

    //  System.out.println(r.left);         
    //  System.out.println(r.right);
        print_t(r.left);
        System.out.println(r.data+" ");
        print_t(r.right);
    }

}


}
public class BST_prac {
public static void main(String[] args) {
    // TODO Auto-generated method stub
    bstrees b1=new bstrees();
    b1.insert(5);
    b1.insert(1);
    b1.print_t();

}

}

It prints out only 5.

Upvotes: 1

Views: 468

Answers (2)

Asif
Asif

Reputation: 1

When you are inserting new node as mentioned by Codor, you are not storing the references of parent node like whether you want to add to left node or right node. always it is creating new node. I have made little changes for making your code work in insert method.

public void insert(int data){
        //creating root node if root node itself is null
        if(root==null){
            root =new Node(data);
        } else {
            root=insert_node(root, data, null, null);
        }
        //System.out.println("after insert root data is " + root.data);
    }
    public Node insert_node(Node node, int n, String dir, Node parent){
        //traverse and insert in proper nodes
        //assign left or right child based on some logic i have taken direction as string here.
        if(node == null) {
            Node n1 = new Node(n);
            if(dir.equalsIgnoreCase("left")) {
                parent.left = n1;
            } else {
                parent.right = n1;
            }
        }
        else if(root.data<=n){
            parent = root;
            insert_node(root.right, n, "right", parent);
        }
        else{
            parent = root;
            insert_node(root.left, n, "left", parent);
        }
        return root;
    }

Upvotes: 0

Codor
Codor

Reputation: 17605

In the call which inserts the value 1 into the tree, the call to insert_node(root.left,n) creates a new node, but no reference to this newly created node is stored, which means that effectively the tree itself is not changed. The reference should be stored in the parent node of the newly created node; the same applies to insertion of nodes into the right subtree.

Upvotes: 3

Related Questions