java binary tree insert function non recursive

Question

I have written a code for inserting to the binary tree an element generic's type which is ordered by their names. Don't think it is correct though.

public boolean insert(E e) {
    BTNode temp = root;
    if (root == null) {
        root.setElement(e);
    }
    while (temp != null)
    if (temp.element().getClass().getName().compareTo(e.getClass().getName()) < 0) {
        temp = temp.getRight();
    } else {
        temp = temp.getLeft();
    }
    temp.setElement(e);
    return true;
}

Can you suggest me corrections ?

@amadeus good try but then the line temp.setElement(e); is always an NPE. — weston
– weston, Commented Oct 7, 2012 at 9:43

weston · Accepted Answer · 2012-10-07 10:13:58Z

An insert would need to create a new node. I don't now how to create them as I haven't see the constuctor, but I suggest something along the lines of:

public boolean insert(E e) {        
    if (root == null) {
        root = new BTNode();
        root.setElement(e); //how would this work with a null root?
        return true; //that's it, we're done (when is this ever false by the way?)
    }
    BTNode current = root; 
    while (true) { //brackets! indenting is important for readabilty
        BTNode parent=current;
        if (current.element().getClass().getName().compareTo(e.getClass().getName()) < 0) {
            current = current.getRight();
            if(current==null) { //we don't have a right node, need to make one
              current = new BTNode();
              parent.setRight(current);
              break; //we have a new node in "current" that is empty
            }
        } else { 
            current= current.getLeft();
            if(current==null) { //we don't have a left node, need to make one
              current = new BTNode();
              parent.setLeft(current);
              break;  //we have a new node in "current" that is empty
            }
        }
    }
    current.setElement(e); 
    return true; 
}

Yasser Safi · Accepted Answer · 2020-11-17 22:26:20Z

1

public Boolean add(int data){
    Node node = new Node(data);
    if(isEmpty()){
        root = node;
    }else{
        Node temp = root;
        while(true){
            if(data < temp.getData()){
                if(temp.getLeft() != null)
                    temp = temp.getLeft();
                else
                    break;
            }else{
                if(temp.getRight() != null)
                    temp = temp.getRight();
                else
                    break;
            }
        }
        if(data < temp.getData())
            temp.setLeft(node);
        else
            temp.setRight(node);
    }
    return true;
}

answered Nov 17, 2020 at 22:26

Yasser Safi

111 bronze badge

Comments

Jack Brown · Accepted Answer · 2012-10-07 10:04:36Z

-2

As amadeus mentioned, the while loop should not have a semicolon at the end :

BTNode temp = root;
    if (root == null) {
        root.setElement(e);
        return;
    }
    while (temp != null)
     {
       if (temp.element().getClass().getName().compareTo(e.getClass().getName()) < 0) {
           if(temp.getRight() != null)
             temp = temp.getRight();
           else
             {
               temp.createRight(e);
               temp = null; //or break
             }
       } else {
           if(temp.getLeft() != null)
             temp = temp.getLeft();
           else
             {
               temp.createLeft(e);
               temp = null; //or break
             }
       }
     }

    return true;

edited Oct 7, 2012 at 10:04

answered Oct 7, 2012 at 9:54

Jack Brown

848 bronze badges

4 Comments

weston Over a year ago

-1 and as I mentioned: Then the line temp.setElement(e); is always an null pointer exception.

Jack Brown Over a year ago

Another solution would be to catch the exception and handle creation of the node in the 'catch' block ... ugly though...

Jack Brown Over a year ago

Guess I missed deleting the last statement .... The element is set earlier in the while loop itself...

user1417426 Over a year ago

you are right @eston temp always point to null pointer exception.. so how can i correct the code for inserting the next element at the correct position?

Collectives™ on Stack Overflow

java binary tree insert function non recursive

3 Answers 3

Comments

Comments

4 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

Comments

4 Comments

Your Answer

Sign up or log in

Post as a guest

Related