Welcome to the Java Programming Forums


The professional, friendly Java community. 21,500 members and growing!


The Java Programming Forums are a community of Java programmers from all around the World. Our members have a wide range of skills and they all have one thing in common: A passion to learn and code Java. We invite beginner Java programmers right through to Java professionals to post here and share your knowledge. Become a part of the community, help others, expand your knowledge of Java and enjoy talking with like minded people. Registration is quick and best of all free. We look forward to meeting you.


>> REGISTER NOW TO START POSTING


Members have full access to the forums. Advertisements are removed for registered users.

Page 1 of 2 12 LastLast
Results 1 to 25 of 42

Thread: find largest value in BST

  1. #1
    Junior Member
    Join Date
    Dec 2012
    Posts
    23
    Thanks
    1
    Thanked 0 Times in 0 Posts

    Default find largest value in BST

    Hi everyone. I have pretty much done all of the coding for my assignment apart from one method.

    The main aim of the assignment is to read in entries from a file and put them into a BST sorted alphabetically. The objects on each node contain a String and a double attribute. The method I am stuck on is to return the largest double. Being as they are sorted in alphabetical order I cannot just call to the right while there is a right node.

    My thinking with the code I pasted in is to get the maximum value from the left hand side and the right hand side. And then to return the larger of those two values. I tried this and I did not actually get the largest. I am thinking that I am missing left nodes on the right hand side and vice versa (fortunately the largest must fall into one of these two categories or I might have missed this error). There is also a largestRight method to mirror what the left one does. I just can't seem to think how to get past this problem. Before this all I was able to do was return the value of the root node's double attribute. This seems to be the closest I have got so far ...

    I am also thinking there is a much simpler solution. I will be very grateful for any help in getting me to understand how to get this right.
    	   public double largest()
    	   {
    		   return largestLeft(root);
    	   }
     
    		private double largestLeft(TreeNode node)
    		{
    			double maxValue = -1.0;
    			while ( node != null )
    			{				
    				if (node.doubleValue > maxValue)
    					maxValue = node.doubleValue;			
    				node=node.left;
    			}
    			return maxValue;
    		}


  2. #2
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    25,042
    Thanks
    63
    Thanked 2,708 Times in 2,658 Posts

    Default Re: find largest value in BST

    How can we test the code to see how it works?
    If you don't understand my answer, don't ignore it, ask a question.

  3. #3
    Junior Member
    Join Date
    Dec 2012
    Posts
    23
    Thanks
    1
    Thanked 0 Times in 0 Posts

    Default Re: find largest value in BST

    Hello Norm

    Sorry for the delay. I didn't want to put all my code for the whole assignment online so I took out the methods not relevant to this problem and made some slight changes. I have checked it compiles.

    ****code now removed so others on the same course can have fun with this****
    I have the text I removed including the code saved in a txt file to put back up if forum staff want me to (preferably after submission deadline though )
    Attached Files Attached Files
    Last edited by Java Bean; December 10th, 2012 at 04:15 PM. Reason: Latest file being used added and coded changed

  4. #4
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    25,042
    Thanks
    63
    Thanked 2,708 Times in 2,658 Posts

    Default Re: find largest value in BST

    What's in the file it ties to read?

    I'm done for tonight, back tomorrow.
    If you don't understand my answer, don't ignore it, ask a question.

  5. #5
    Junior Member
    Join Date
    Dec 2012
    Posts
    23
    Thanks
    1
    Thanked 0 Times in 0 Posts

    Default Re: find largest value in BST

    It reads the file fine. It is the method that the problem is with. I have made a dummy file and added it to the post. It will probably not have the same result because the data is different, but the programming is exactly the same.

  6. #6
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    25,042
    Thanks
    63
    Thanked 2,708 Times in 2,658 Posts

    Default Re: find largest value in BST

    I have made a dummy file and added it to the post. It will probably not have the same result because the data is different
    If you have not used the file and proved that it causes the error, then it is a waste of time for me to use it. You need to post data that causes the error.
    If you don't understand my answer, don't ignore it, ask a question.

  7. #7
    Junior Member
    Join Date
    Dec 2012
    Posts
    23
    Thanks
    1
    Thanked 0 Times in 0 Posts

    Default Re: find largest value in BST

    I will create a file that exactly replicates the same issue. After that I will try something that has occurred to me that might work.

    Basically my reason for this is that this is a public forum and therefore the code I have put up in addition to my initial post could be copied. I am just trying to limit that whilst giving enough detail to ask the question. I am sorry if that is causing the problem.

    The method with the problem is to search for the biggest value of the double value. My idea is to split the problem into two halves, the (left and the right hand sides), to get the maximum on each side then compare the two to get the largest in the entire tree. What I am asking is for help in understanding how to get this right or even a more elegant way (as long as I can understand it).

    I realise that detail is needed. I am just trying to avoid possible copying issues unneccesarily

  8. #8
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    25,042
    Thanks
    63
    Thanked 2,708 Times in 2,658 Posts

    Default Re: find largest value in BST

    You don't need another file for testing. You need to verify that the file you posted shows the error,

    If the code only looks on one side of the tree, how will it find something that could be on the other side?

    Some debugging ideas:
    Add a toString() method to the Node class that returns the data in the node and the left and right nodes.
    In the BST printing the value of root will then print out the whole contents of the tree.
    If you don't understand my answer, don't ignore it, ask a question.

  9. #9
    Junior Member
    Join Date
    Dec 2012
    Posts
    23
    Thanks
    1
    Thanked 0 Times in 0 Posts

    Default Re: find largest value in BST

    I found using a print statement very useful in helping me to get to the solution of another method that had been troubling me. I pretty much understand why it is not returning the correct value in that I can see it does not search EVERY node. So basically I need to work out how to get it to check the nodes it misses out at the moment. Being as I know the maximum value it was easy to spot. Had it been on a node along the path that is actually checked I might not have noticed and thought it was a job well done (which it isn't).

    I have a method to print the entire tree sorted in alphabetical order. As well as other methods required in the assignment. I decided to leave them out as explained already.

    Here is what I have so far on that method with a file which definitely replicates the same wrongly returned value.

    	 public double largest()
    	   {
    		 if (largestLeft(root) > largestRight(root))
    		   return largestLeft(root);
    		 else return largestRight(root);
    	   }
     
    		private double largestLeft(Node node)
    		{
    			double maxValue = -1.0;
    			while ( node != null )
    			{				
    				if (node.doubleValue > maxValue)
    					maxValue = node.doubleValue;			
    				node=node.left;
    			}
    			return maxValue;
    		}
     
    		private double largestRight(Node node)
    		{
    			double maxValue = -1.0;
    			while ( node != null )
    			{				
    				if (node.doubleValue > maxValue)
    					maxValue = node.doubleValue;			
    				node=node.right;
    			}
    			return maxValue;
    		}

    I will be going out soon so if I do not reply after this that is the reason but I will keep an eye on the thread on my phone and hope to solve this tonight before I go to bed so all I need to do is the comments and write the report for it. I am still thinking there is a much shorter solution so I will be thinking about that when I get a chance.
    Attached Files Attached Files

  10. #10
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    25,042
    Thanks
    63
    Thanked 2,708 Times in 2,658 Posts

    Default Re: find largest value in BST

    it does not search EVERY node.
    It would have to look at all the nodes.
    If you don't understand my answer, don't ignore it, ask a question.

  11. #11
    Junior Member
    Join Date
    Dec 2012
    Posts
    23
    Thanks
    1
    Thanked 0 Times in 0 Posts

    Default Re: find largest value in BST

    Quote Originally Posted by Norm View Post
    It would have to look at all the nodes.
    I realised it was not checking all the nodes when I looked for an explanation for it returning the wrong value. My first effort to put it right so it searches all nodes caused it to just return the value on the root node. So what I have done here is show that I am thinking on this rather than just wanting the code handed out. My trouble is I haven't yet worked out how to get it to check all the other nodes. I will of course try again when I get back in later and I will monitor the thread while I am gone.

  12. #12
    Junior Member
    Join Date
    Dec 2012
    Posts
    23
    Thanks
    1
    Thanked 0 Times in 0 Posts

    Default Re: find largest value in BST

    Quote Originally Posted by Norm View Post

    Some debugging ideas:
    Add a toString() method to the Node class that returns the data in the node and the left and right nodes.
    In the BST printing the value of root will then print out the whole contents of the tree.
    I am still stuck with this. Whilst I said I can see why my previous effort is failing, I still have not found a way to get this right.

    I am not sure what you mean with the first suggestion. The second suggestion seems a bit like the inorder traversal (method not included in this thread) which outputs all the data successfully. If that is what you mean, I have tried something like that and made a local variable for the biggest value which I compared with each nodes corresponding value and if the current nodes value was bigger that value was assigned to the maxValue variable. The problem is that when I called it from a public method it just returned the value of the corresponding attribute in the root. (this method was recursive)

    So I am asking now, should I continue to find a way to get my method I posted to work or is it just never going to work. Or should I try to find a way to get the previous effort I tried (explained above - not posted but can if needed), or is that also never going to work. I must be missing something here. A lot of time is going into this single method without success.

  13. #13
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    25,042
    Thanks
    63
    Thanked 2,708 Times in 2,658 Posts

    Default Re: find largest value in BST

    I am not sure what you mean with the first suggestion. The second suggestion
    The two suggestions go together. By adding a toString() method to the Node class and then printing root( a Node) the compiler will generate calls to the Node class's toString() method that will print out all the Node objects in the tree.

    I thought you had a method that looked at all the nodes in the tree. Can that be modified to find a value as it goes through the tree?
    If you don't understand my answer, don't ignore it, ask a question.

  14. #14
    Junior Member
    Join Date
    Dec 2012
    Posts
    23
    Thanks
    1
    Thanked 0 Times in 0 Posts

    Default Re: find largest value in BST

    Sorry for the delay in responding. I had other classes today and there is work for them also

    Quote Originally Posted by Norm View Post
    I thought you had a method that looked at all the nodes in the tree. Can that be modified to find a value as it goes through the tree?
    I am back to doing this again. I have put in several print statements in to see what is happening to my variables (I added another variable for testing purposes). So I can see that as every node is visited the variables are altered (as they should be). However I also notice that each variable is reinitialised to 0 when the method moves to each node. This is something I know I need to understand how to stop happening.

    But even with this, I would expect the returned maxValue to be equal to the attribute of the last node visited as EVERY nodes corresponding attribute is greater than 0. But the returned maxValue is the root's attribute.

  15. #15
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    25,042
    Thanks
    63
    Thanked 2,708 Times in 2,658 Posts

    Default Re: find largest value in BST

    Do you have code that will compile, execute and show what you are talking about?
    If you don't understand my answer, don't ignore it, ask a question.

  16. #16
    Junior Member
    Join Date
    Dec 2012
    Posts
    23
    Thanks
    1
    Thanked 0 Times in 0 Posts

    Default Re: find largest value in BST

    In the BinarySearchTree class I have put these methods which replace the largest() methods previously posted. (I have replaced formatting in my actual code to be submitted work with spaces between the attributes - this doesn't affect the functionality).

    	   private double inorderHelper(Node node)
    	    {
    	      double x = 0;
    	      double y = 0;
     
    	        if (node == null) return 0;
     
     
    	        inorderHelper(node.left);
    	        System.out.println(node.stringData +"                     " + node.doubleValue);
    	        System.out.println("           x is  "+x);
    	        System.out.println("           y is  "+y);
     
    	        y = Math.max(x, node.doubleValue);
    	        System.out.println("           x is  "+x);
    	        System.out.println("           y is  "+y);
    	        System.out.println();
    	        x = y;
    	        System.out.println("           x is  "+x);
    	        System.out.println("           y is  "+y);
    	        System.out.println();System.out.println();
    	        System.out.println(" Final value of y is  "+y);System.out.println();
    	        inorderHelper(node.right);
    	       return y;
    	    }
     
    	public double returnMax()
    	{
    		return inorderHelper(root);
    	}

    In the TreeTest class I have added this line of code.

    System.out.println("y is equal to    " + t.returnMax());

  17. #17
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    25,042
    Thanks
    63
    Thanked 2,708 Times in 2,658 Posts

    Default Re: find largest value in BST

    Please post code for testing that will compile, execute and show the problem. What you posted won't compile.
    If you don't understand my answer, don't ignore it, ask a question.

  18. #18
    Junior Member
    Join Date
    Dec 2012
    Posts
    23
    Thanks
    1
    Thanked 0 Times in 0 Posts

    Default Re: find largest value in BST

    I didn't get my edit in quick enough

    It compiless now. Sorry.

  19. #19
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    25,042
    Thanks
    63
    Thanked 2,708 Times in 2,658 Posts

    Default Re: find largest value in BST

    Which post is the code in? Posts are numbered in upper right. This is post #19
    If you don't understand my answer, don't ignore it, ask a question.

  20. #20
    Junior Member
    Join Date
    Dec 2012
    Posts
    23
    Thanks
    1
    Thanked 0 Times in 0 Posts

    Default Re: find largest value in BST

    It is in post #3

    I have also edited it to have the file I am currently working from in the same thread.

    Maybe I should have edited the code there also.

  21. #21
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    25,042
    Thanks
    63
    Thanked 2,708 Times in 2,658 Posts

    Default Re: find largest value in BST

    I don't see any debugging output when the program executes. All it prints is: 1.04

    For testing I'd make as small a tree as possible to keep the debug print out down.
    If you don't understand my answer, don't ignore it, ask a question.

  22. #22
    Junior Member
    Join Date
    Dec 2012
    Posts
    23
    Thanks
    1
    Thanked 0 Times in 0 Posts

    Default Re: find largest value in BST

    I have made a file which shows the output I am seeing (attached to this post).

    I have also edited the code in post #3 which should be exactly the same as what I am using at the moment
    Attached Files Attached Files

  23. #23
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    25,042
    Thanks
    63
    Thanked 2,708 Times in 2,658 Posts

    Default Re: find largest value in BST

    Please post the debug output on the forum.

    I don't see the toString() method in the Node class.

    The printlns generate too many lines of output. x and y could be printed on the same line.


    Which of the three classes did you change? Can you put all the classes into one file so I don't have to copy and paste three files.
    If you don't understand my answer, don't ignore it, ask a question.

  24. #24
    Junior Member
    Join Date
    Dec 2012
    Posts
    23
    Thanks
    1
    Thanked 0 Times in 0 Posts

    Default Re: find largest value in BST

    I haven't done the toString() method in the Node class, mainly because I haven't worked out what you meant yet (I will probably realise in the morning after I have slept but I doing what I can while I am still up).

    Can you put all the classes into one file so I don't have to copy and paste three files.
    Did you want me to upload the .java files?

  25. #25
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    25,042
    Thanks
    63
    Thanked 2,708 Times in 2,658 Posts

    Default Re: find largest value in BST

    Here's what prints out with:
     System.out.println(root);
    when there is a toString() method in the Node class.

    { S=Hyena, d=0.53, l={ S=Hamster, d=0.29, l={ S=Beetle, d=1.04, l={ S=AddedForTestingCount, d=1.0, l=null, r=null}, r={ S=Bobcat, d=0.78, l=null, r={ S=Carp, d=0.62, l=null, r={ S=Flounder, d=0.4, l={ S=Cat, d=1.68, l=null, r={ S=Cobalt, d=1.18, l=null, r=null}}, r=null}}}}, r=null}, r={ S=Lynx, d=0.59, l=null, r={ S=Nightjar, d=0.52, l={ S=Nematode, d=0.35, l=null, r=null}, r={ S=Ox, d=0.45, l=null, r={ S=Songbird, d=1.71, l={ S=PolarBear, d=2.16, l=null, r=null}, r={ S=Zebra, d=1.07, l=null, r=null}}}}}}
    If you don't understand my answer, don't ignore it, ask a question.

Page 1 of 2 12 LastLast

Similar Threads

  1. 3x3 array find largest number
    By joecan2010 in forum Loops & Control Statements
    Replies: 1
    Last Post: November 27th, 2012, 11:56 PM
  2. Dictionary using Distributed Hash Table and BST Tree
    By dezett in forum What's Wrong With My Code?
    Replies: 28
    Last Post: June 23rd, 2012, 12:03 PM
  3. Write a method that searches the BST for a given input
    By Jurgen in forum Algorithms & Recursion
    Replies: 4
    Last Post: January 6th, 2012, 11:46 AM
  4. Find the two largest number
    By vendettabf in forum What's Wrong With My Code?
    Replies: 15
    Last Post: December 29th, 2011, 01:23 PM
  5. [SOLVED] Can someone verify if this code for deleting a BST works?
    By scottb80 in forum Java Theory & Questions
    Replies: 2
    Last Post: November 2nd, 2010, 10:19 AM