Solved

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

Posted on 2004-10-03
28
247 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
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 12
  • 8
  • 8
28 Comments
 
LVL 92

Expert Comment

by:objects
ID: 12215133
>      return Math.abs(countLeft - countRight);


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

Expert Comment

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

Expert Comment

by:CEHJ
ID: 12215292
>>At the point your recursive call happens

(in insert)
0
PeopleSoft Has Never Been Easier

PeopleSoft Adoption Made Smooth & Simple!

On-The-Job Training Is made Intuitive & Easy With WalkMe's On-Screen Guidance Tool.  Claim Your Free WalkMe Account Now

 
LVL 92

Expert Comment

by:objects
ID: 12215300
>      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
ID: 12219727
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
ID: 12219830
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
ID: 12220173
Read my comment again carefully and you should see why
0
 
LVL 92

Expert Comment

by:objects
ID: 12221481
>      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
ID: 12221509
Already said that ;-)
0
 
LVL 92

Expert Comment

by:objects
ID: 12221541
:-D
0
 

Author Comment

by:tyweed420
ID: 12222062
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
ID: 12222107
I'll let CEHJ clarify it seeing's how he reckons he already answered the question ;)
0
 

Author Comment

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

Expert Comment

by:objects
ID: 12223792
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
 
LVL 86

Expert Comment

by:CEHJ
ID: 12224632
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
ID: 12224640
thats whats already being done

0
 
LVL 86

Expert Comment

by:CEHJ
ID: 12224659
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
ID: 12230975
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
ID: 12232707
0
 
LVL 92

Expert Comment

by:objects
ID: 12232709
>  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
ID: 12232914
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
ID: 12232922
sorry, misread the code.
0
 

Author Comment

by:tyweed420
ID: 12232998
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
ID: 12233158
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
ID: 12240125
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
ID: 12244355
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
ID: 12246403
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
ID: 12272630
8-)
0

Featured Post

Industry Leaders: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

Question has a verified solution.

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

Java had always been an easily readable and understandable language.  Some relatively recent changes in the language seem to be changing this pretty fast, and anyone that had not seen any Java code for the last 5 years will possibly have issues unde…
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…
This tutorial explains how to use the VisualVM tool for the Java platform application. This video goes into detail on the Threads, Sampler, and Profiler tabs.
Viewers will learn how to properly install Eclipse with the necessary JDK, and will take a look at an introductory Java program. Download Eclipse installation zip file: Extract files from zip file: Download and install JDK 8: Open Eclipse and …

688 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