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.

kindly post your full code on pastebin.com or ide.geeksforgeeks.org as I am unable to see what the above code segment trying to do. — Brij Raj Kishore
– Brij Raj Kishore, Commented Sep 28, 2018 at 1:40
The above code segment is getting values stated in the input, it is supposed to construct a binary tree from these values by taking the first one setting that as the root, then building the rest returning true value where if it has added it. If it gets an duplicate it doesn't do anything it just returns false because it doesn't insert the value. I am sure the issue is somewhere in the if statements but with my limited skills i am unable to see it. All this needs to be achieved while keeping the tree inorder. — Masteprh33r
– Masteprh33r, Commented Sep 28, 2018 at 1:52
from the above code what I could infer is that your are also getting o/p as false at every insertion. I could be be guessing wrong and it depends completely on the implementation you made. So kindly paste whole code classes so as it would give a broader picture. — Brij Raj Kishore
– Brij Raj Kishore, Commented Sep 28, 2018 at 3:22

Masteprh33r · Accepted Answer · 2018-09-28 03:46:48Z

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;                                              
        }

cleberz · Accepted Answer · 2018-09-28 03:02:53Z

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.

Collectives™ on Stack Overflow

Method to insert into a binary tree problem

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related