?
Solved

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

Posted on 2004-10-06
7
Medium Priority
?
79 Views
Last Modified: 2012-06-08
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
0
Comment
Question by:tyweed420
7 Comments
 
LVL 37

Expert Comment

by:zzynx
ID: 12243561
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;


 }
0
 
LVL 14

Expert Comment

by:Tommy Braas
ID: 12243599
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
0
 
LVL 37

Expert Comment

by:zzynx
ID: 12243672
>> 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;
}
0
Never miss a deadline with monday.com

The revolutionary project management tool is here!   Plan visually with a single glance and make sure your projects get done.

 
LVL 37

Expert Comment

by:zzynx
ID: 12243686
Correction (forgot to change):

      if (t == null) {
         root = new BSTNode(x,null,null);
         return;
      }
0
 
LVL 86

Accepted Solution

by:
CEHJ earned 2000 total points
ID: 12244019
I've rearranged the code so that the main class is BinaryTreeTester, so save it into a new directory as the file BinaryTreeTester.java to compile and run:





// SNIP=========================================================


class BinarySearchTree {

      BSTNode root;
      int height;

      BinarySearchTree() {
            root = null;
      }


      public BSTNode insert(int x, BSTNode t) {
            if (t == null) {
                  t = new BSTNode(x, null, null);
            }
            else {
                  if (x <= t.getData()) {
                        t.leftChild = insert(x, t.leftChild);
                  }

                  else {
                        t.rightChild = insert(x, t.rightChild);
                  }
            }
            return t;
      }

      public int height() {

            int countLeft = 0;
            int countRight = 0;
            BSTNode search = new BSTNode(Integer.MIN_VALUE, root, null);
            while (search.leftChild != null) {
                  countLeft++;
                  search.leftChild = search.leftChild.leftChild;
            }

            search = new BSTNode(Integer.MAX_VALUE, null, root);

            while (search.rightChild != null) {
                  countRight++;
                  search.rightChild = search.rightChild.rightChild;
            }

            System.out.println("Count left = " + countLeft);
            System.out.println("Count right = " + countRight);
            return Math.max(countLeft, countRight);

      }


}
//end

public class BSTNode {


      int data;
      BSTNode leftChild;
      BSTNode rightChild;

      BSTNode(int k, BSTNode leftChild, BSTNode rightChild) {
            data = k;
            this.leftChild = leftChild;
            this.rightChild = rightChild;
      }

      BSTNode(int k) {
            this(k, null, null);
      }

      public int getData() {
            return data;
      }
}

public class BinaryTreeTester {


      public static void main(String[] args) {

            BinarySearchTree tree = new BinarySearchTree();
            tree.root = tree.insert(5, null);
            tree.insert(4, tree.root);
            tree.insert(3, tree.root);
            tree.insert(6, tree.root);
            tree.insert(7, tree.root);
            tree.insert(8, tree.root);
            tree.insert(9, tree.root);
            System.out.println("Tree height = " + tree.height());

      }
      //end main

}
0
 
LVL 92

Expert Comment

by:objects
ID: 12244357
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);
      }
   }
}
0
 
LVL 86

Expert Comment

by:CEHJ
ID: 12246383
8-)
0

Featured Post

The new generation of project management tools

With monday.com’s project management tool, you can see what everyone on your team is working in a single glance. Its intuitive dashboards are customizable, so you can create systems that work for you.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

For beginner Java programmers or at least those new to the Eclipse IDE, the following tutorial will show some (four) ways in which you can import your Java projects to your Eclipse workbench. Introduction While learning Java can be done with…
Basic understanding on "OO- Object Orientation" is needed for designing a logical solution to solve a problem. Basic OOAD is a prerequisite for a coder to ensure that they follow the basic design of OO. This would help developers to understand the b…
Viewers learn about the scanner class in this video and are introduced to receiving user input for their programs. Additionally, objects, conditional statements, and loops are used to help reinforce the concepts. Introduce Scanner class: Importing…
Viewers will learn about the different types of variables in Java and how to declare them. Decide the type of variable desired: Put the keyword corresponding to the type of variable in front of the variable name: Use the equal sign to assign a v…
Suggested Courses
Course of the Month5 days, 15 hours left to enroll

588 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question