Solved

can someone tell me why i can't get the height of a binary search treee!

Posted on 2004-10-03
28
232 Views
Last Modified: 2010-03-31
I have 3 classes BSTNode, BinarySearchTree, and BinarySearchTreeTester. I'm simply trying to insert objects then get the height of tree. However when i insert and call height method in my tester class i get
0
0
0

I think my insert is correct. However my getHeight is most likely the problem.However the logic seems ok. Please if someone can look at my code tell me if my getheight() is wrong or is it my insert its gotta be one of the two.

oh also i'm a bity confused in the tester class when you insert you have two parameters 1. the element 2. the reference to another node.

i'm not sure how you would for example add 4 to a tree

tree.insert(4,null);

would this insert 4 and everything below would be null. If this is the case this is not what im looking for if there is a 3 below i dont want it to go away so would
tree.insert(4,root) be what im looking for
========

public class BinarySearchTree
{

  BSTNode root;
  int height;


  BinarySearchTree()
  {
        root = null;
  }

 public BSTNode insert(int x, BSTNode t)
 {
       if(t == null)
       return t = new BSTNode(x,null,null);

      else if(x < t.getData())
       t.leftChild = insert(x,t.leftChild);


      else if( x > t.getData() )
       t.rightChild = insert(x,t.rightChild);

       return t;


 }


public int height()
{
   
      int countLeft=0;
      int countRight=0;
    BSTNode search = root;
      while (search != null)
      {
            search.leftChild = search.leftChild.leftChild;
            countLeft++;
      }

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

      return Math.abs(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;
      }








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


     BinarySearchTree tree = new BinarySearchTree();
     tree.insert(2,tree.root);
     System.out.println(tree.height());
     tree.insert(4,tree.root);
     System.out.println(tree.height());
     tree.insert(66,tree.root);
     System.out.println(tree.height());
      tree.insert(3,tree.root);
     System.out.println(tree.height());



  }//end main




 }//end
==============
0
Comment
Question by:tyweed420
  • 12
  • 8
  • 8
28 Comments
 
LVL 92

Expert Comment

by:objects
Comment Utility
>      return Math.abs(countLeft - countRight);


shouldn't that be the max of the two?
0
 
LVL 86

Expert Comment

by:CEHJ
Comment Utility
At the point your recursive call happens, right and left are null, so it won't grow
0
 
LVL 86

Expert Comment

by:CEHJ
Comment Utility
>>At the point your recursive call happens

(in insert)
0
 
LVL 92

Expert Comment

by:objects
Comment Utility
>      if(t == null)
>      return t = new BSTNode(x,null,null);

looks like that should be:

      if(t == null)
      return root = new BSTNode(x,null,null);

0
 

Author Comment

by:tyweed420
Comment Utility
This just frustrates me so bad!  i have the dumb fixes that i needed to change thanks. However i'm still not able to add to the tree. It seems to want to set every value to root everytime . I just don't understand this. Look at this tester class. i'll put the out put to the right of each.

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

     BinarySearchTree tree = new BinarySearchTree();
     tree.insert(5 ,null);                                                     //root
     System.out.println(tree.height());                             //0
     System.out.println(tree.root.getData() + "data");        //5 data
     System.out.println("");

     tree.insert(4,tree.root);                                      //root    <======== why is it going into root again??? and then goes left i don't get it
                                                                             //left
     System.out.println(tree.height());                         //0
     System.out.println(tree.root.getData() + "data");       //4 data
     System.out.println("");

     tree.insert(66,tree.root);                                  //root     <=============== goes into root again? it should not tree.root should not be null
                                                                           //right
     System.out.println(tree.height());                      //0
     System.out.println(tree.root.getData() + "data");    66 data
      System.out.println("");

     tree.insert(3,tree.root);
     System.out.println(tree.height());
     System.out.println(tree.root.getData() + "data");




  }//end main




 }//end class


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


public class BinarySearchTree
{

  BSTNode root;
  int height;


  BinarySearchTree()
  {
        root = null;
  }

 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())
      {
       t.leftChild = insert(x,t.leftChild);
              System.out.println("left");

    }

      else if( x > t.getData() )
      {
       t.rightChild = insert(x,t.rightChild);
              System.out.println("right");

    }

       return t;


 }


public int height()
{

      int countLeft=0;
      int countRight=0;
    BSTNode search = root;
    if(search !=null)
    {

          while (search.leftChild != null)
          {
            search.leftChild = search.leftChild.leftChild;
            countLeft++;
          }
   }

      search = root;

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

      return Math.max(countLeft,countRight);


}



}//end
0
 

Author Comment

by:tyweed420
Comment Utility
I should be using tree.root as the second parameter in my insert in the testing class right


tree.insert(4,tree.root) so it starts at the root it just makes sense to me to have to start at the root. so if this is correct and my insert method is correct ....... what could be the culprit?
0
 
LVL 86

Expert Comment

by:CEHJ
Comment Utility
Read my comment again carefully and you should see why
0
 
LVL 92

Expert Comment

by:objects
Comment Utility
>      t.leftChild = insert(x,t.leftChild);

you need to first check if t.leftChild is null and deal with appropriately if it is.
Calling insert with null would cause it to replace your root node.
0
 
LVL 86

Expert Comment

by:CEHJ
Comment Utility
Already said that ;-)
0
 
LVL 92

Expert Comment

by:objects
Comment Utility
:-D
0
 

Author Comment

by:tyweed420
Comment Utility
I just increased it to 150 so you guys split the points. i really do appreciate the help. I'm slowly understanding java now with all the help.

quick question though since i need top check if t.leftChild and t.rightChild are null i put in this iif else statement. However in my test class after i do this call and i call
tree.root.leftChild it is null??? i'v drawn the picture it seems simple you have a root and its children are null. You then enter the statement if t.leftchild == null you simple set root.leftchild = new BSTNode(x,null,null). but this is not working do i need to somehow refer the leftchild pointer back up to root?

thanks cehj & objects!

if(t.leftChild == null)
            {
                  root.leftChild = new BSTNode(x,null,null);

                              System.out.println("left child null");

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

Expert Comment

by:objects
Comment Utility
I'll let CEHJ clarify it seeing's how he reckons he already answered the question ;)
0
 

Author Comment

by:tyweed420
Comment Utility
Come on objects thats no fair.I really need help on this man........
0
 
LVL 92

Expert Comment

by:objects
Comment Utility
you don't seem to set the return node correctly.
insert() doesn't need to return a node at all as far as I can see so I would suggest removing it.

0
What Should I Do With This Threat Intelligence?

Are you wondering if you actually need threat intelligence? The answer is yes. We explain the basics for creating useful threat intelligence.

 
LVL 86

Expert Comment

by:CEHJ
Comment Utility
I'm pretty busy at the moment so cannot spend much time on this. But as far as the 'perpetual root' problem is concerned, instead of

>>
     else if(x < t.getData())
      t.leftChild = insert(x,t.leftChild);
>>

you need to do something like:

      else if (x < t.getData()) {
            if (t.leftChild == null) {
                  // create a new node and assign to t.leftChild
            }
            else {
                  t.leftChild = insert(x, t.leftChild);
            }
      }

but i would suggest you google for some examples (there are bound to be some Java ones out there) as, for one thing, you need to also handle node data equality


0
 
LVL 92

Expert Comment

by:objects
Comment Utility
thats whats already being done

0
 
LVL 86

Expert Comment

by:CEHJ
Comment Utility
I didn't notice changes had been made to that part. As i said, i've no time to spend on this now, but a quick glance suggests to me that the assignment i suggested in the code's comment is *not* being done
0
 

Author Comment

by:tyweed420
Comment Utility
ok i'v taken everything you have both told me and implemented it. All except the node duplicates because we are not suppose to handle duplicates at this time.I'v done these following changes.

1. if t.leftChild or t.rightChild are null cr4eate new node and assign to the child
2. i created a insert(int x) to handle implementing a integer
3. Objects - i was taught that insert needs to return a node because it must insert a node correct? could you explain why it should not return a node all the examples i'v looked at have the format my insert method has. however the only difference is that mine does not work!

========== Binary Search Tree==================================================
public class BinarySearchTree
{

  BSTNode root;
  int height;


  BinarySearchTree()
  {
        root = null;

  }

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


 public BSTNode insert(int x, BSTNode t)
 {
       if(t == null)
       {
            System.out.println("root");
          return  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");

            }
            else
            {
            t.leftChild = insert(x,t.leftChild);
            //root = insert(x,root);
               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);
            }
            else
            {
             t.rightChild = insert(x,t.rightChild);
             //root = insert(x,root);

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


 }


public int height()
{

      int countLeft=0;
      int countRight=0;
    BSTNode search = root;
    if(search !=null)
    {
            System.out.println("height left child" + search.leftChild);

          while (search.leftChild != null)
          {
            search.leftChild = search.leftChild.leftChild;
            countLeft++;
          }
   }

      search = root;
    if(search !=null)
    {
                        System.out.println("height right child" + search.leftChild);

       while (search.rightChild != null)
      {
           search.rightChild = search.rightChild.rightChild;
           countRight++;
        }
    }
      return Math.max(countLeft,countRight) +1;


}



}//end
==========================================

==========test class and output it gives i just dont get what is going wrong. i'm missing an assignment statement somewhere,.=========
class BinaryTreeTester
{
  public static void main(String [] args)
  {

     BinarySearchTree tree = new BinarySearchTree();

     tree.insert(5);
     System.out.println(tree.height() + " height test");  //    height of 1 so far correct
     System.out.println(tree.root.getData() + "data");  // 5 data so far ok
     System.out.println(tree.root); //not null ok looking good

     System.out.println("");  // this is where everything gets @#$ up

     tree.insert(4);                        //goes into the leftChild == null area so creates t.left= new node (x,null,null)
     System.out.println(tree.height() + " height test");  // height is now 2 looks like it may work
     System.out.println(tree.root.getData() + "data");   // still 5 data
     System.out.println(tree.root.leftChild);                // this is the wierd thing this shows as null?? where did the 4 go? hieght recognized it and incremented?

     System.out.println("");

     tree.insert(66,tree.root);    // this goesinto the rchild == null
     System.out.println(tree.height() + " height test");  // height is still 2
     System.out.println(tree.root.getData() + "data");
     System.out.println(tree.root.rightChild);            // its null but suppose to be the reference to the 66 whats going on? do i need to assign these new nodes up to root somehow

      System.out.println("");

     tree.insert(3,tree.root);
     System.out.println(tree.height() + " height test");
     System.out.println(tree.root.getData() + "data");




  }//end main




 }//end class


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

thank you again you both for your help i'm trying my best to learn this on my own but i'm stuck so i must ask you two genuises.............. i'll increase points for you guys
0
 
LVL 92

Expert Comment

by:objects
Comment Utility
0
 
LVL 92

Expert Comment

by:objects
Comment Utility
>  tree.insert(4);                        //goes into the leftChild == null area so creates t.left= new node (x,null,null)

this will replace the root won't it.
0
 

Author Comment

by:tyweed420
Comment Utility
tree.insert(4); should replace the root however it doesnt.it stays 5, which was the previos insert
0
 
LVL 92

Expert Comment

by:objects
Comment Utility
sorry, misread the code.
0
 

Author Comment

by:tyweed420
Comment Utility
hey np , does my code not look correct? is it something simple you want me to figure out on my own or is it pretty vague where the problem is?
0
 
LVL 92

Expert Comment

by:objects
Comment Utility
did you have a look at the link I posted above, including the implementation at:
http://www.javaworld.com/javaworld/jw-11-1996/indepth/BinarySearchTree.java
0
 

Author Comment

by:tyweed420
Comment Utility
yes i'v gone through it. It's not helping because it is not a recursive insertion of a binary search tree. Objects what would you suggest i do? Anyone out there good with trees that can peek t this insertion method. it seems to still give me problems when the leftchild and right child are null and there uis just a root. So for example i call tree.insert(5); it inserts 5. but then after if i call tree.insert(4) it goes into the first insert method then calls the second insert which then goes into the
if(t.leftChild == null) statement. it should replace the 5 with 4 as a root.

furthermore if i give tree.insert(4,tree.node) it should add 4 to the left child of 5 which is at root however it goews into the same if statement

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

            }

this should assign a new node to the t.leftChild however the next line of code in my testTree is System.out.println(tree.root.leftChild); guess what i get.thats right null!! ahhhhhh it should be a damn 4 why why why. Iknow tis is some simple assignment statement but i can not figure it out

THE PERSON WHO FIGURES IT OUT GETS 500 POINTS I NEED TO MOVE ON PLEASE HELP............
 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)
       {
          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");

            }
            else
            {
            t.leftChild = insert(x,t.leftChild);
            //root = insert(x,root);
               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);
            }
            else
            {
             t.rightChild = insert(x,t.rightChild);
             //root = insert(x,root);

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


 }
0
 
LVL 92

Expert Comment

by:objects
Comment Utility
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

Accepted Solution

by:
CEHJ earned 200 total points
Comment Utility
Since objects has posted the same code into both of your questions, i shall do the same ;-)
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 86

Expert Comment

by:CEHJ
Comment Utility
8-)
0

Featured Post

Maximize Your Threat Intelligence Reporting

Reporting is one of the most important and least talked about aspects of a world-class threat intelligence program. Here’s how to do it right.

Join & Write a Comment

For customizing the look of your lightweight component and making it look lucid like it was made of glass. Or: how to make your component more Apple-ish ;) This tip assumes your component to be of rectangular shape and completely opaque. (COD…
This was posted to the Netbeans forum a Feb, 2010 and I also sent it to Verisign. Who didn't help much in my struggles to get my application signed. ------------------------- Start The idea here is to target your cell phones with the correct…
Viewers learn about the “while” loop and how to utilize it correctly in Java. Additionally, viewers begin exploring how to include conditional statements within a while loop and avoid an endless loop. Define While Loop: Basic Example: Explanatio…
Viewers will learn about the regular for loop in Java and how to use it. Definition: Break the for loop down into 3 parts: Syntax when using for loops: Example using a for loop:

772 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

Need Help in Real-Time?

Connect with top rated Experts

12 Experts available now in Live!

Get 1:1 Help Now