incrementing a count in a binary search tree insert word count method

I am searching a string of text for word, putting the words in a bst, and if the word reappears, tring to increment a count in the node. Here is the method and would appreciate advice. The node should keep the word and the count as well as left and right.
Here is some of the code, and I have high lited where it is not operating as I want. Advice would be appreciated. Thanks

class BST
{
      BSTNode root;
                   Integer count, test, value;

      public BST()
      {
               root = null;
      }

      public void insert(String newVal)
      {
            BSTNode newNode = new BSTNode(newVal);

      if (root == null){
                      root = newNode;
                  root.count = 1;
                  System.out.println(root.info+"("+root.count+")");
      }

                      else if (newVal.equals(root.info)){
                      root.count+=1;
                      System.out.println(root.info+"("+root.count+")");              
                      }

      else
      {
            BSTNode p, prev;
            p = root;
            prev = p;
//****** this section does not work as I (expect)(want)*******
                                       while (p != null)
                 {
                  prev = p;

                                           if (newVal.equals(p.info))
                                       {
                                          p.count+=1;
                                System.out.println(p.info+"("+p.count+")");
                                               }
                                           if (newVal.compareTo(p.info) < 0)
                        p = p.left;
                        else
                        p = p.right;
                   }

            if (newVal.compareTo(prev.info) < 0)
                        prev.left = newNode;
                  else
                        prev.right = newNode;
//************************************************            }
      }

}

class BSTNode
{
        String info;
        int count;
        BSTNode left, right;

      public BSTNode(String newVal)
      {
            info = newVal;
                                int count = 1;
            right = null;
            left = null;
      }
}

 
LVL 1
dennisryan01Asked:
Who is Participating?
I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

JakobACommented:
If you write a few comments in your code we (and you) wil have a better chance of knowing what your are trying to do.

In this sort of algorithm the object references (prev and p) are key. they contain different objects at different times through the iteration, so a debug method that often work is to track them.

say to yourself  "I am now tracking 'prev'!"   (later you track 'p' the same way)
go thrugh your code and every place 'prev' is used consider what you are doing there and why
     what value are you setting in prev?
     what will it be used for?
     should it be set earlier?
     are you setting it too early? (losing a reference you will need later)
     what value are you getting from prev here?
     is it the right one?
     etc.
it is ok to take notes while doing this :-))

regards JakobA
0
dennisryan01Author Commented:
good point. The code is hard to read (and it would help if I had a better handle on what I was doing) It will take me a couple of hours until I can get back to it. thks
0
grim_toasterCommented:
What do you mean by not operating as you want?  There is one small problem, your counter variable in your BSTNode class is being initialised to 0, not the 1 as you would think by quickly glancing at the constructor, as the constructo is:

     public BSTNode(String newVal)
     {
          info = newVal;
                                int count = 1;
          right = null;
          left = null;
     }

When it should be:

     public BSTNode(String newVal)
     {
          info = newVal;
          count = 1;
          right = null;
          left = null;
     }
0
Keep up with what's happening at Experts Exchange!

Sign up to receive Decoded, a new monthly digest with product updates, feature release info, continuing education opportunities, and more.

grim_toasterCommented:
Also, there are a few other things you could do to improve your code, for example, do you want to handle the same words but different case, also your call to compareTo could be used once to also cater for your equals (avoids the same checks twice), by comparing to 0.  But I think I know what your problem is, usually these sort of tree node approach's are carried out using some form of recursive call (method calls itself) to go through the list, your approach will work, but I'm presuming that if the word exists you only want to increment a counter, not create a new instance of it?  In which case, when you increment the counter, you would probably want to exit out of the method:

 if (newVal.equals(p.info))
                                     {
                                         p.count+=1;
                                System.out.println(p.info+"("+p.count+")");
                                return;
                                             }

Although not the most elegant way to do things, it should work.  Also, whilst you are commenting your code, it might be helpful to distinguish between you System.out calls, as they all look identical, so how would you know which one is called?
0

Experts Exchange Solution brought to you by

Your issues matter to us.

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Start your 7-day free trial
dennisryan01Author Commented:
grim_toaster
I think you hit exactly what I want to do, exit out, but my logic does not support it.  I could probably have used flags as well. Will try later to see if it executes, and let you know.  

If it were elegant, how does it look?
0
grim_toasterCommented:
Your logic does support it, the return statement can be used to exit out of the method.  The reason it's not perfectly elegant is that it's best to only have one exit point from a method as it makes the code more readable.  As for the recursive thing, it would depend upon how large your tree will get, your method is fine, as recursion is only really effective for finite sized trees (as you can get stack problems).

I'll see if I can knock together a quick example for you.
0
grim_toasterCommented:
Here's some code for you to think over anyway:

import java.util.StringTokenizer;

public class Thing
{
    public static void main(String args[])
    {
        String text = "the quick brown fox jumped over the lazy old cat quick the jumped";
        StringTokenizer st = new StringTokenizer(text);
        Thing tmp = new Thing();
       
        while (st.hasMoreTokens())
        {
            String next = st.nextToken();
            tmp.insert(next);
        }
    }

    BSTNode root = null;

    public void insert(String newVal) {
        if (root == null) {
            root = new BSTNode(newVal);
        }
        else {
            BSTNode p = root;

            while (p != null) {
                int compared = newVal.compareToIgnoreCase(p.info);

                if (compared == 0) {
                    p.count++;
                    break;
                }
                else if (compared < 0) {
                    if (p.left == null) {
                        p.left = new BSTNode(newVal);
                        break;
                    }
                    else {
                        p = p.left;
                    }
                }
                else {
                    if (p.right == null) {
                        p.right = new BSTNode(newVal);
                        break;
                    }
                    else {
                        p = p.right;
                    }
                }
            }
        }
    }
}

class BSTNode
{
    final String info;
    int count = 1;
    BSTNode left;
    BSTNode right;

    public BSTNode(String newVal)
    {
        this.info = newVal;
    }    
}
0
dennisryan01Author Commented:
excellent  "return" worked

almost finished here, but what makes this wrong?

class BSTNode
{
        String info;
        int count;
        BSTNode left, right;

     public BSTNode(String newVal)
     {
          info = newVal;
          int count = 1;  <- what did this do

          right = null;
          left = null;
     }
}
0
dennisryan01Author Commented:
grim_toaster

(opps   pushed wrong button )

almost finished here, but what makes this wrong?

class BSTNode
{
        String info;
        int count;
        BSTNode left, right;

     public BSTNode(String newVal)
     {
          info = newVal;
          count = 1;     <- what did this do
          int count=1;   <-instead of this(besides work properly, I mean)
          right = null;
          left = null;
     }
}
0
JakobACommented:
when you write
     int count
you are declaring a new wariable to live in the current scope. ie, you ar creating a variable local to the BSTnode constructor. An entirely different variable than the  count  that is declared as a variable outside the constructor.
0
grim_toasterCommented:
Exactly!

Also, as a seperate point, if you want to be able to do this sort of thing just using the standard libraries. you can use the code below, considerably smaller and easier to maintain, and also less likely to have a bug in there (the stadard API's are tried and tested methods!), then you can use the TreeMap to get a list of the keys (keySet()), get an iterator on it, to go through the list:

    TreeMap treeMap = new TreeMap();

    public void insert(String newVal) {
        Object out = treeMap.get(newVal);
       
        if (out != null) {
            ((BSTNode) out).count++;
        }
        else {
            treeMap.put(newVal, new BSTNode());
        }
    }

    private class BSTNode {
        int count = 1;    
    }
0
dennisryan01Author Commented:
Thank you for your help yesterday.  Unfortunately we are doing it the hard way, and now that I can increment, I want to search the tree to find the info string with the greatest length.  I can search the tree for the highest count (most often used word) successfully, but am in trouble on recursively searching and returning the string.  It is a separate question which I will be posting in about 30 minutes.

again, thanks for your time and assistance.
0
grim_toasterCommented:
Not a problem!  But to actually search for the largest String, the code to iterate through the list would be no different from what you would have used to get the highest count, the only difference would be that you are using a different item to search on, so instead of

if (obj.count > highestCount)

you would use:

if (obj.info.length() > highestLength)
0
dennisryan01Author Commented:
of course, I did it the highest count differently
posting question in a minute
0
It's more than this solution.Get answers and train to solve all your tech problems - anytime, anywhere.Try it for free Edge Out The Competitionfor your dream job with proven skills and certifications.Get started today Stand Outas the employee with proven skills.Start learning today for free Move Your Career Forwardwith certification training in the latest technologies.Start your trial today
Java

From novice to tech pro — start learning today.

Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.