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.

Code :

---

	   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;
		}

---

How can we test the code to see how it works?

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:)) )

What's in the file it ties to read?

I'm done for tonight, back tomorrow.

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.

Quote:

---

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.

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 ;)

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.

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.

Code :

---

	 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.

Quote:

---

it does not search EVERY node.

---

It would have to look at all the nodes.

Quote:

---

Originally Posted by Norm

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.

Quote:

---

Originally Posted by Norm

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.

Quote:

---

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?

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

Quote:

---

Originally Posted by Norm

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.

Do you have code that will compile, execute and show what you are talking about?

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).

Code :

---

	   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.

Code :

---

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

---

Please post code for testing that will compile, execute and show the problem. What you posted won't compile.

I didn't get my edit in quick enough :eek:

It compiless now. Sorry.

Which post is the code in? Posts are numbered in upper right. This is post #19

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.

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.

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

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.

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).

Quote:

---

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?

Here's what prints out with:

Code :

---

 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}}}}}}