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

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.

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

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.

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.

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.

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

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.

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

I didn't get my edit in quick enough

It compiless now. Sorry.

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

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?