Method to insert into a binary tree problem

Question

I have an issue with inserting into a binary tree, the following code doesn't seem to work the way i want it to.

  public static <E extends Comparable<? super E>>
                                   boolean inorderInsert(BTree<E> T, E x) {

   BTreeNode<E> n = T.getRoot();
    if(T.getRoot() == null) {
        T.setRoot(new BTreeNode<E>(x));
    }


 while (n != null) {
         if (x.compareTo(n.getElement()) == 0)
             return false;
         else if (x.compareTo(n.getElement()) < 0)
         if(n.getLeftChild()==null) {
             n.setLeftChild(new BTreeNode<E> (x));
         }
         if(n.getLeftChild()!=null) {
             n=n.getLeftChild();
         }
         else
         if(x.compareTo(n.getElement()) > 0) {
         if(n.getRightChild()==null) {
             n.setRightChild(new BTreeNode<E> (x));
         }
         if(n.getRightChild()!=null ) {
             n=n.getRightChild();
         }
         }
     } // while
    return true;

}

with following inputs:

             10 3 8 4 10 5 5 18 19 13 

code produces the following output:

             3 4 5 13 18 19 8 10  

instead of:

             3 4 5 8 10 13 18 19 10 

i was thinking about making a tree in a way that it would come out as:

                         10
                      __/  \__
                     3         18                                                             
                      \       /  \
                       8     13  19                                               
                      /  
                     4
                      \ 
                       5

I can't find where i went wrong. Any help would be greatly appreciated.

Answer 1

When i went over the code i found what was wrong, this code produced the desired results.

    boolean inorderInsert(BTree<E> T, E x) {
    BTreeNode<E> n = T.getRoot();
    if(T.getRoot() == null) {
        T.setRoot(new BTreeNode<E>(x));
    }


    while (n != null) {
        if (x.equals(n.getElement()))                            
        return false;                                                             
else if (x.compareTo(n.getElement()) < 0)                  
        if (n.getLeftChild() == null) {                            
        n.setLeftChild(new BTreeNode<E>(x));                      
        return true;                                              
        }           
        else         
        n = n.getLeftChild();                                                                                                    
else  if (n.getRightChild() == null){                            
        n.setRightChild(new BTreeNode<E>(x));                   
        return true;                                               
        }
        else   
        n = n.getRightChild();                                  
        }
        return false;                                              
        }

Answer 2

From the comments on the original question, it appears that what you're trying to do is a Tree Sort, which is usually easier to implement as a recursive algorithm, not an iterative (while loop). I recommend taking a look at the literature to learn more about the algorithm. The way the code above currently is written (iteratively, that is, using a for loop), will only allow you to traverse a single node of the tree per iteration, making the resulting data structure be linear, that is, each node will only have a single child (in other words, it will be equivalent to a list).

Also, I highly recommend indenting the code properly as it makes it a lot easier to understand exactly where the code is branching to.