Link to home
Start Free TrialLog in
Avatar of tyweed420
tyweed420

asked on

I cannot get my binary search tree to grow when i call my insert method

I have three classes BSTNode,BinarySearchTree, and BinaryTreeTester

 all i have to do is implement the insert(int x,BSTNode t) and i'm good. However this has become a nightmare! I have traced through all my code and can see what is going wrong, however i have been unable to fix the problem. I'm desperate and am going to put this thread at 500 points. So big guys objects cehj we have discussed this many times please help!! Ok here are the two importantr classes ill post vbinary search tree first and then below this i'll post the tester with the output to the side . In a nutshel when i call insert the first time it sets root up just fine. but all following calls cause unexpected results look at binary test to see.

=======================================

public void insert(int x)
 {
    root = insert(x,root);
    System.out.println("insert(int x)");
 }


 public BSTNode insert(int x, BSTNode t)
 {
       if(t == null)
       {
            System.out.println("root");
          return  root = new BSTNode(x,null,null);
     }

      else if(x < t.getData())
      {
            if(t.leftChild == null)
            {
                  t.leftChild = new BSTNode(x,null,null);
                  System.out.println("left child null");
                  printTree();

            }
            else
            {
            t.leftChild = insert(x,t.leftChild);
            System.out.println("left");
        }
    }

      else if( x > t.getData() )
      {
            if(t.rightChild == null)
            {
                  System.out.println("right child null");
                  t.rightChild = new BSTNode(x,null,null);
                                      printTree();
            }
            else
            {
             t.rightChild = insert(x,t.rightChild);


                System.out.println("right");
        }
    }
  else
  ; //do nothing

System.out.println("returning t");
       return t;


 }





======================================

class BinaryTreeTester
{
  public static void main(String [] args)
  {

     BinarySearchTree tree = new BinarySearchTree();

     tree.insert(5);                                          calls insert(int k)
     System.out.println(tree.height() + " height test"); height of 1
     System.out.println(tree.root.getData() + "data");  data is 5
     System.out.println(tree.root);                               //is not null good.............

     System.out.println("");

     tree.insert(4);                                    calls insert(int k) this calls insert(x,root)  it goes into the second insert method and ends up in the if(t.leftChild == null) statement and places it ok i print the tree within the binary search tree class i get 5 4 it worked    however in the tester class tree.root.leftchild is null? why?    
     System.out.println(tree.height() + " height test");
     System.out.println(tree.root.getData() + "data");
     System.out.println(tree.root.leftChild + "left child");  this is null

     System.out.println("");

     tree.insert(66);              this does same thing is called by insert(int k) then called by insert(int x,bstnode t) then goes into the if (t.rightycild == null) and if i call print tree in the binary search tree class i get 5 root, 66 rightchild ........... 4 is gone?
     System.out.println(tree.height() + " height test");
     System.out.println(tree.root.getData() + "data");
     System.out.println(tree.root.rightChild + "right child"); once again now in the tester class rightchild is null?

      System.out.println("");

     tree.insert(3);  //allthe same i get 5 3 for tree if calle in the binarysearch tree with a printtree method but in the tester nothing
     System.out.println(tree.height() + " height test");
     System.out.println(tree.root.getData() + "data");

       System.out.println("========PRINT TREE============");
     tree.printTree();  then i call print tree in the tester i get 5 ??



  }//end main




 }//end


It must be with the childs == null statements and somehow assignments are lost when i call from another class i just cant get this.

500 POINTS AND A BIG HUG & KISS TO ANY WHO CAN HELP ME PLEASE
Avatar of zzynx
zzynx
Flag of Belgium image

I think the idea is to return the newly created BSTNode isn't it?
Then I think it should be:

public void insert(int x) {
    insert(x,root);                                      // <<<<<<<< not root =
    System.out.println("insert(int x)");
}

public BSTNode insert(int x, BSTNode t)  {
     if(t == null) {
          System.out.println("root");
         return  root = new BSTNode(x,null,null);   // here the inital root is set (once)
     }

     else if(x < t.getData())
     {
          if(t.leftChild == null)
          {
               t.leftChild = new BSTNode(x,null,null);
               System.out.println("left child null");
               printTree();
               // <<<<<<<<<<<< here I would return t.leftChild;
          }
          else
          {
             System.out.println("left");
             t.leftChild = insert(x,t.leftChild);   // <<<<<<<<<<<< shouldn't this be   return insert(x,t.leftChild);
        }
    }

     else if( x > t.getData() )
     {
          if(t.rightChild == null)
          {
               System.out.println("right child null");
               t.rightChild = new BSTNode(x,null,null);
                                     printTree();
               // <<<<<<<<<<< here I would return t.rightChild
          }
          else
          {
             System.out.println("right");
            t.rightChild = insert(x,t.rightChild);   // <<<<< shouldn't this be    return insert(x,t.rightChild);
        }
    }
  else
  ; //do nothing           // <<<<<<<<< What about double values????

System.out.println("returning t");
      return t;


 }
Hi tyweed420,

Try the following:

 public BSTNode insert(int x, BSTNode t)
 {
      if(t == null)
      {
          System.out.println("root");
         return  root = new BSTNode(x,null,null);
     }

     else if(x < t.getData())
     {
          if(t.leftChild == null)
          {
               t.leftChild = new BSTNode(x,null,null);
               System.out.println("left child null");
               printTree();

          }
          else
          {
           t.leftChild.insert(x, t.leftChild);
           System.out.println("left");
        }
    }

     else if( x > t.getData() )
     {
          if(t.rightChild == null)
          {
               System.out.println("right child null");
               t.rightChild = new BSTNode(x,null,null);
                                     printTree();
          }
          else
          {
            t.rightChild.insert(x, t.rightChild);


              System.out.println("right");
        }
    }
  else
  ; //do nothing

System.out.println("returning t");
      return t;
 }


Cheers!

\\t
>> Orangehead

I don't think you can do

        t.leftChild.insert(x, t.leftChild);

since this insert() function isn't defined on a BSTNode but on the BinarySearchTree


>>tyweed420
Even, why should insert(int x, BSTNode t) return something?
I think that's not necessary. The insert function just has to insert a new node into the tree.

This is the most easiest form I believe:


public void insert(int x) {
    insert(x,root);
    System.out.println("insert(int x)");
}

public void insert(int x, BSTNode t) {

     if(t == null)
          return  root = new BSTNode(x,null,null);   // here the inital root is set (once)
     else if(x < t.getData()) {
          if(t.leftChild == null)
               t.leftChild = new BSTNode(x,null,null);
          else
             insert(x,t.leftChild);
          return;
     }
     else if( x > t.getData() ) {
          if(t.rightChild == null)
               t.rightChild = new BSTNode(x,null,null);
          else
               insert(x,t.rightChild);
          return;
    }
    else
        ; //do nothing  // <<<<<<<<< What about double values????

    return;
}
Correction (forgot to change):

      if (t == null) {
         root = new BSTNode(x,null,null);
         return;
      }
ASKER CERTIFIED SOLUTION
Avatar of CEHJ
CEHJ
Flag of United Kingdom of Great Britain and Northern Ireland image

Link to home
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
Start Free Trial
try something like this:

public void insert(int x)
{
   insert(x, root);
}

private void insert(int x, BSTNode t)
{
   if (t==null)
   {
      root = new BSTNode(x, null, null);
   }
   else if (x<t.getData())
   {
      if (t.leftChild==null)
      {
         t.leftChild = new BSTNode(x, null, null);
      }
      else
      {
         insert(x, t.leftChild);
      }
   }
   else
   {
      if (t.rightChild==null)
      {
         t.rightChild = new BSTNode(x, null, null);
      }
      else
      {
         insert(x, t.rightChild);
      }
   }
}
8-)