Binary Search Tree height

[syn3rgyz]

I'm trying to write a method that recursively finds the height of the deepest node of a tree.
my professor predefined most of the nodes and trees and I just need to fill in the method.

public int calculateTreeLevels()
	{
// ADD YOUR CODE HERE
		if(root == null){
			return 0;
		}
		else{
			return 1 + max(root.leftNode.calculateTreeLevels(), root.rightNode.calculateTreeLevels());
			
		}
	}

I get an error that says the method calculateTreeLevels is undefined for the type TreeNode.
How can I write a recursive method if I cant even call the method itself.
Can someone explain to me why it is doing this/what im doing wrong and how I might bypass this problem.

 

[nameless_centurian]

hint:

to use member methods of an object, the method in question must actually be a member of said object. it all depends on where/how you define the method.

 

[syn3rgyz]

hint:

to use member methods of an object, the method in question must actually be a member of said object. it all depends on where/how you define the method.

I had to read what you said 5 times before i understood it lol
My professor just told me to fill out that empty method, so I dont think I can move the method to inside the object.

 

[Cyrilix]

Well, you only have two choices. Either the function has to be a member function of the node class, or it has to be able to receive a node as a parameter, so you can do it globally or as a class method, but there's no way you can do it without "changing" the function itself, whether it be the signature, or the location.

 

[syn3rgyz]

Well, you only have two choices. Either the function has to be a member function of the node class, or it has to be able to receive a node as a parameter, so you can do it globally or as a class method, but there's no way you can do it without "changing" the function itself, whether it be the signature, or the location.

that was my first thought too... i probably need the method to receive a parameter, but my professor gave me this to fill out

public int calculateTreeLevels()
	{
// ADD YOUR CODE HERE

	}

so i guess entering parameters is not a choice, but i cant move the method around either.. arghh

 

[svet-am]

that was my first thought too... i probably need the method to receive a parameter, but my professor gave me this to fill out

public int calculateTreeLevels()
    {
// ADD YOUR CODE HERE

    }

so i guess entering parameters is not a choice, but i cant move the method around either.. arghh

No, the function() notation is normal when referring to a method, even if that method requires parameters. It's a common notation that we use in industry all the time.

Give it all the parameters you need to get the job done unless your professor explicitly says otherwise.

 

[syn3rgyz]

No, the function() notation is normal when referring to a method, even if that method requires parameters. It's a common notation that we use in industry all the time.

Give it all the parameters you need to get the job done unless your professor explicitly says otherwise.

the thing is in another java file he included he called the method like this

int treeLevels = tree.calculateTreeLevels();

so i guess i cant add any parameters

 

[fluxion]

it's a member function of the class that "tree" is an instance of then. not sure what you mean by not being allowed to move it...did he give you a skeleton framework to use and explicitly defined it somewhere else? or did you just give you that little snippet of code out of context so you can place it where you see fit?

 

[ameoba]

Either...

a) you're not showing us everything you have

b) this isn't expected to compile/run

c) it's assumed you are going to add the method to a class



Since it seems the instructions are ambiguous, the best solution is to just ask the instructor. Really - you're allowed to do that - it's part of why you pay so much money to take the classes. If you'd sent him an email, you probably would be done with this by now.

 

[syn3rgyz]

Either...

a) you're not showing us everything you have

b) this isn't expected to compile/run

c) it's assumed you are going to add the method to a class



Since it seems the instructions are ambiguous, the best solution is to just ask the instructor. Really - you're allowed to do that - it's part of why you pay so much money to take the classes. If you'd sent him an email, you probably would be done with this by now.

thats what i did actually but i thought id post the question here too while i wait for his reply. he just replied me and he said that I should use a private helper method that does work recursively. I dont really understand how it's going to work but im thinking it through right now.

and also there are 3 java files and they are all very long but i'll attach the java file that the method belongs to.

import java.util.Iterator;

/*
 * YOU MUST FILL IN THE CODE FOR THE FOLLOWING TWO METHODS:
 * - calculateTreeLevels 
 * - rebalance
 */

public class DJIABinarySearchTree
{
	// ROOT FOR OUR TREE
	private TreeNode root = null;
	
	// TOTAL NUMBER OF NODES IN THE TREE
	private int size = 0;
	
	/*
	 * Default constructor, it does nothing
	 */
	public DJIABinarySearchTree() {}
	

	// ACCESSOR METHOD
	public int size() { return size; }
	
	/*
	 * DO NOT CHANGE THIS METHOD
	 * 
	 * This method adds a company to the correct sorted location
	 * in the BST by employing the recursive addCompanyToNode method.
	 */
	public void addCompany(DJIACompany initCompany)
	{
		// CASE: EMPTY TREE
		if (root == null)
		{
			// MAKE IT THE ROOT, THE ONE AND ONLY NODE
			root = new TreeNode(initCompany, null, null);
			size++;
		}
		else
		{
			// addCompanyToNode WILL FIND THE PLACE TO PUT IT,
			// STARTING WITH THE ROOT
			addCompanyToNode(root, initCompany);
		}
	}
	
	/*
	 * DO NOT CHANGE THIS METHOD
	 * 
	 * This method recursively searches for the appropriate
	 * place in this BST to add the company.
	 */
	private void addCompanyToNode(TreeNode node, DJIACompany initCompany)
	{
		// NO DUPLICATES
		if (node.data.getSymbol().equals(initCompany.getSymbol()))
			return;
		
		// ADD TO LEFT SUBTREE
		if (node.data.getSymbol().compareTo(initCompany.getSymbol()) > 0)
		{
			// ADD IT AS A LEAF, WE CAN'T GO ANY FURTHER LEFT
			if (node.leftNode == null)
			{
				node.leftNode = new TreeNode(initCompany, null, null);
				size++;
			}
			else
			{
				// TRY FURTHER LEFT
				addCompanyToNode(node.leftNode, initCompany);
			}
		}
		// ADD TO RIGHT SUBTREE
		else
		{
			// ADD IT AS A LEAF, WE CAN'T GO ANY FURTHER RIGHT
			if (node.rightNode == null)
			{
				node.rightNode = new TreeNode(initCompany, null, null);
				size++;
			}
			else
			{
				// TRY FURTHER RIGHT
				addCompanyToNode(node.rightNode, initCompany);
			}
		}
	}

	/*
	 * DO NOT CHANGE THIS METHOD
	 * 
	 * This method empties the tree of all nodes.
	 */
	public void clear()
	{
		root = null;
		size = 0;
	}

	/*
	 * YOU MUST DEFINE THIS METHOD
	 * 
	 * It calculates the level of the deepest node in the tree. Note,
	 * if the tree only has a root, then it only has one level.
	 * 
	 * ADVICE: Look at how I recursively defined the addCompanyToNode
	 * method. You might want to try to do something like that for this as well.
	 */
	public int calculateTreeLevels()
	{
// ADD YOUR CODE HERE
		if(root == null){
			return 0;
		}
		else{
			return 1 + Math.max(this.root.leftNode.calculateTreeLevels(), root.rightNode.calculateTreeLevels());
			
		}
	}
		
	
	
	/*
	 * DO NOT CHANGE THIS METHOD
	 * 
	 * This method is used for rendering purposes. It's used to calculate
	 * the position of each node such that we get a nice, aligned looking
	 * tree.
	 */
	public int calculateTreeIndex(DJIACompany company)
	{
		return calculateTreeIndex(root, company, 0);
	}

	/*
	 * DO NOT CHANGE THIS METHOD
	 * 
	 * This method is a recursive helper to calculateTreeIndex
	 */
	private int calculateTreeIndex(TreeNode node, DJIACompany company, int index)
	{
		if (node == null)
			return -1;
		int comparison = node.data.getSymbol().compareTo(company.getSymbol());
		if (comparison == 0)
			return index;
		else if (comparison > 0)
		{
			int leftIndex = (2 * index) + 1;
			return calculateTreeIndex(node.leftNode, company, leftIndex); 
		}
		else
		{
			int rightIndex = (2 * index) + 2;
			return calculateTreeIndex(node.rightNode, company, rightIndex);
		}
	}

	/*
	 *	YOU MUST DEFINE THIS METHOD
	 *
	 * 	This method should rearrange the node so as to minimize the height
	 * 	of the tree and to balance the tree on right and left sides. Again,
	 *  might want to think about using a recursive helper method.
	 */
	public void rebalance()
	{
// YOUR CODE GOES HERE
		public boolean isBalanced(){
			if(root == null){
				return true;
			}
			int depth = Treemode
				
			}
		}
	}
	
	
	/*
	 * DO NOT CHANGE THIS METHOD
	 * 
	 * This method produces an iterator that produces elements in
	 * sorted order.
	 */
	public Iterator treeIterator()
	{
		return new SortedIterator();
	}

	
	/*
	 * DO NOT CHANGE THIS CLASS
	 * 
	 * This iterator produces data from the tree in sorted order.
	 */
	class SortedIterator implements Iterator
	{
		protected DJIACompany[] elements = new DJIACompany[size];
		protected int currentElement = 0;
		
		public SortedIterator()
		{
			if (root != null)
			{
				fillIteratorElements(root);
				currentElement = 0;
			}
		}
		
		private void fillIteratorElements(TreeNode node)
		{
			if (node.leftNode != null)
				fillIteratorElements(node.leftNode);
			elements[currentElement] = node.data;
			currentElement++;
			if (node.rightNode != null)
				fillIteratorElements(node.rightNode);
		}
		
		public boolean hasNext()
		{
			if ((size > 0) && (currentElement < size))
				return true;
			else
				return false;
		}
		
		public Object next()
		{
			if ((size > 0) && (currentElement < size))
				return elements[currentElement++];
			else
				return null;
		}
		
		public void remove(){}
	}
}

class TreeNode
{
	protected DJIACompany data;
	protected TreeNode leftNode;
	protected TreeNode rightNode;
	
	public TreeNode(DJIACompany initData,
					TreeNode initLeftNode,
					TreeNode initRightNode)
	{
		data = initData;
		leftNode = initLeftNode;
		rightNode = initRightNode;
	}
}

 

[RedShark]

Based on the code and your comment, it looks like you want to add a method to the class TreeNode that will return the height of the node. This is where the recursion will be.

 

[syn3rgyz]

i added the recursive part to the treenode class so now it looks like

class TreeNode
{
	protected DJIACompany data;
	protected TreeNode leftNode;
	protected TreeNode rightNode;
	
	public TreeNode(DJIACompany initData,
					TreeNode initLeftNode,
					TreeNode initRightNode)
	{
		data = initData;
		leftNode = initLeftNode;
		rightNode = initRightNode;
	}
	public int height()
	{
		if(this == null){
			return 0;
		}
		else{
			return 1 + Math.max(this.leftNode.height(), this.rightNode.height());
		}
	}
}

then i changed the method to call the recursive function

public int calculateTreeLevels()
	{
// ADD YOUR CODE HERE
		return this.root.height();
	}

when i compile and try to run the program though it seems like it doesnt work, did i do it right?

 

[generelz]

A simple test case and a run through a debugger will quickly illuminate where things are going wrong. As it stands right now, I'm surprised you're not seeing a NullPointerException.

Have you learned about this concept yet? What happens when you try to do something with a null reference? Can you figure out where you might be running into this problem?

Can you tell me why the following line of code:

if ( this == null)

Is flawed in a very fundamental way?

 

[syn3rgyz]

I'm fairly new to java since i just transfered schools and my old school taught python, so im not quite sure whats wrong with it, my guess it is because this could be any type of object?

i tried to use root instead of this but it says root cannot me resolved.

 

[nameless_centurian]

remember that "this" is the object that the current method is a member of. member methods can only be called from objects.

why is it wrong to test if this==null?

edit: this is not specific to java.

 

[syn3rgyz]

is it because it is calling on the object itself?

 

[LuminaryJanitor]

he just replied me and he said that I should use a private helper method that does work recursively. I dont really understand how it's going to work but im thinking it through right now.

First of all, you should be defining your recursive method in the tree class rather than the node class, and you should be passing nodes as arguments to this recursive function.

The problem with this is that the user can't use it. The root of the tree is private, so the user can't possibly make the first recursive call.

This is where helper functions come in. The solution is to define a function which the user can call, whose sole purpose is to make the first recursive call (by providing the details which the user doesn't need to know about) and relay the final result.


BTW, did you define the node class yourself, or was it given to you? Because it really shouldn't be accessible to the user... It's another one of those details which the tree class should keep to itself. The user doesn't need to know that a tree is built from nodes - all they need (and therefore, all they should be given) are the tree's public methods.

One last thing... even if you end up throwing it away, make sure you understand what's wrong with your current height() method. Like previous posters mentioned, it's not Java-specific - it's something pretty fundamental in any OO language, Python included.

 

[syn3rgyz]

First of all, you should be defining your recursive method in the tree class rather than the node class, and you should be passing nodes as arguments to this recursive function.

The problem with this is that the user can't use it. The root of the tree is private, so the user can't possibly make the first recursive call.

This is where helper functions come in. The solution is to define a function which the user can call, whose sole purpose is to make the first recursive call (by providing the details which the user doesn't need to know about) and relay the final result.


BTW, did you define the node class yourself, or was it given to you? Because it really shouldn't be accessible to the user... It's another one of those details which the tree class should keep to itself. The user doesn't need to know that a tree is built from nodes - all they need (and therefore, all they should be given) are the tree's public methods.

One last thing... even if you end up throwing it away, make sure you understand what's wrong with your current height() method. Like previous posters mentioned, it's not Java-specific - it's something pretty fundamental in any OO language, Python included.

I didnt define the node class myself it was given, I still dont understand whats wrong with my height method, i guess its cause i dont really understand how to use "this".
After reading what you said im trying to create a helper method that provides the root so i can call it recurvsively

 

[generelz]

I didnt define the node class myself it was given, I still dont understand whats wrong with my height method, i guess its cause i dont really understand how to use "this".
After reading what you said im trying to create a helper method that provides the root so i can call it recurvsively

Think about it for a little while. Your comparison this == null assumes that "this" could be null at some point. My argument is that situation is 100% impossible. The reason why is a very fundamental concept in OO programming, and it's something you need begin to grasp very quickly in order to fix other problems you're having.

The best way to go about this might be to construct a line of code or a "test" to attempt to get that "if" case to evaluate to true. For example, if I provided you with the following class:

class NullTest {
  public boolean amINull() {
     if (this == null)
       return true;
     else
       return false;
  }
}

I'm asking you to write a couple lines of code that would make the "amINull" function return true. Can you do it? What happens when you run that program?

 

[nameless_centurian]

is it because it is calling on the object itself?

you are close. what i am saying is this (in pseudocode):

public class SomeClass{

  public SomeClass(){
     //the constructor
   }

  public void compareObj(SomeClass sc){
/*remember that this and sc are references to an object in memory... let's see if they point to the same object*/
     if(sc == this)
        print "hey, they point to the same place!";
     else
       print "no, they do not";
  }
}

and then in main, do this:

SomeClass sc  = new SomeClass();

sc.compareObj(sc);

what results do you get? what can you conclude from this example?

 

[KaosDG]

Maybe it's me...

But I don't see any way of doing this recursively without passing parameters into the function.

You could also "cheat" by making the parameter have a default value. (This would satisfy the "int treeLevels = tree.calculateTreeLevels();" case)

 

[LuminaryJanitor]

...i guess its cause i dont really understand how to use "this".

Ahh, now I see what you're having trouble with... I took a closer look at your code, and your excessive use of "this" started bringing back memories of Python. I was wrong before when I said it's the same in all OO languages, because I think Python does things quite differently in places.

IIRC, in Python, a method belongs to the class, and the particular object you're working with is just the first argument of that method. So you can call a method on a null object, and the method runs as usual, with one of its arguments as "null".

Java is different - you can think of the method as belonging to the object, kind of like the way a variable belongs to an object.

The first thing this means is that you can ease off the use of "this" a bit... While you're in a call to somenode.height(), the inside of somenode is your environment. All variables and methods inside this object can be referenced by name alone (i.e. you can just say "leftNode" instead of "this.leftNode", and you could call height() on the current object with "height()" rather than "this.height()").

But more importantly, because the method belongs to the object, if the object doesn't exist then the method doesn't either. That is, if somenode is null, and you call somenode.height(), Java will just throw up an exception and crash, because somenode doesn't have that method.

This leads us to the two problems with your height() method:
- Because you know leftNode and rightNode may be null, you need to check them before you try to call methods on them.
- "this" can never be null - if your program is running the height() method, then it's running the height() method of some particular object, and so clearly that object must exist.

 

[nameless_centurian]

what is the status of this assignment.

do understand "this" yet?

 

[syn3rgyz]

i still dont understand it ive been talking about it with my professor for a week now, he just sent me the solution and im studying it.
hes not much of a help though, I have to do another homework based on trees now, so I'm trying to do that one as of now. He doesnt really provide me with help until the assignment is due.

 

[mikeblas]

Many students are taught to think of trees recursively, but I think that few of them are ever tought why trees are the subjects of recursion.

Recursion is a natrual solution (though, not always the best solution) when something big is defined in terms of something smaller.

Let's investigate that. Say I have a binary search tree with a string in each node.

struct
{
	string str;
	struct *pLeft;
	struct *pRight;
};

An empty tree is represented by a pointer to NULL. You don't have any nodes; just a pointer to NULL. Let's write code to handle that case:

int GetTreeHeight( struct *pTree )
{
   if ( pTree == NULL )
      return 0;
}

Well, good. That works for some cases. What if there is data in the node? Say I have this tree:

	string = "mike"
	  pLeft -> NULL
	  pRight -> NULL

It's height is one. How can we make the GetTreeHeight function recurse to find that? We know that if we have data, we've got one more height than whatever is further below is. That is, the tree is defined in terms of this node that I'm looking at right now, plus the subtree to the left below, and the subtree to the right below. If I have data, then, I know I have one more than the height of the height of the tree below me on the right to the left, or the tree on the right below me -- whichever is bigger.

Say I have this tree:

	string = "mike"
	  pLeft -> 
	  	string = "joe"
	  	  pLeft -> NULL
	  	  pRight -> NULL
	  pRight -> NULL

The height is two, right? at "Mike", the height is 1 plus the bigger of the two below. To the right, the height is zero. The height to the left is one.

Let's code that.

int GetTreeHeight( struct *pTree )
{
   if ( pTree == NULL )
      return 0;
   int nLeftHeight = find the left subtree height;
   int nRightHeight = find the right subtree height;
   
   // add one to the bigger of the two heights below us
   // and return it as our answer
   return 1 + max( nLeftHieght, nRightHeight );
}

In this code, though, how do we find the height of the subtrees below us? The answer is recursion; just call the GetTreeHeight() function passing in that sub tree and have ourselves figure out it again.

int GetTreeHeight( struct *pTree )
{
   if ( pTree == NULL )
      return 0;
   int nLeftHeight = GetTreeHeight( pTree->pLeft );
   int nRightHeight = GetTreeHeight( pTree->Right );
   
   // add one to the bigger of the two heights below us
   // and return it as our answer
   return 1 + max( nLeftHieght, nRightHeight );
}

We can step through this using the second mike and joe example above. We call the function with a pointer to "mike", the root node of the tree.

It sees that pTree isn't null, so we don't return zero. We take the pointer to the left sub tree, which points to "joe", and call ourselves again.

So we're back at the beginnig. pTree isn't null, it points at Joe. We again call GetTreeHeight(), but that's the base case; we're passing NULL, so we know it returns zero. Same for the right side. At this point, nLeftHeight = 0, and nRightHeight = 0.

The max of 0 and 0 is zero, and we add one to that, and return it ... we return 1.

We're back in the first instance of the function, then, with nLeftHeight = 1. We have to call GetTreeHeight() on pRight from the "mike" node, which is NULL and will return zero. Here, then, nLeftHeight = 1 and nRightHeight = 0.

The max of 1 and 0 is 1, and we add one to that, which is two. We return it.

The idea is to decompose the problem into simpler stuff. The height of an empty tree is zero. How is any non-zero tree different in height than the empty tree? Well, we don't know, becaue we don't know how many levels we have. We know it's one more than the rest of the levels, though, because we just consumed a level. So we add one to a function that figures out the levels of the deeper nodes. We can do that recursively as many times as we need to (or, at least, as many times as our stack space will allow.)

I hope that helps.

 

[syn3rgyz]

Many students are taught to think of trees recursively, but I think that few of them are ever tought why trees are the subjects of recursion.

Recursion is a natrual solution (though, not always the best solution) when something big is defined in terms of something smaller.

Let's investigate that. Say I have a binary search tree with a string in each node.

struct
{
	string str;
	struct *pLeft;
	struct *pRight;
};

An empty tree is represented by a pointer to NULL. You don't have any nodes; just a pointer to NULL. Let's write code to handle that case:

int GetTreeHeight( struct *pTree )
{
   if ( pTree == NULL )
      return 0;
}

Well, good. That works for some cases. What if there is data in the node? Say I have this tree:

	string = "mike"
	  pLeft -> NULL
	  pRight -> NULL

It's height is one. How can we make the GetTreeHeight function recurse to find that? We know that if we have data, we've got one more height than whatever is further below is. That is, the tree is defined in terms of this node that I'm looking at right now, plus the subtree to the left below, and the subtree to the right below. If I have data, then, I know I have one more than the height of the height of the tree below me on the right to the left, or the tree on the right below me -- whichever is bigger.

Say I have this tree:

	string = "mike"
	  pLeft -> 
	  	string = "joe"
	  	  pLeft -> NULL
	  	  pRight -> NULL
	  pRight -> NULL

The height is two, right? at "Mike", the height is 1 plus the bigger of the two below. To the right, the height is zero. The height to the left is one.

Let's code that.

int GetTreeHeight( struct *pTree )
{
   if ( pTree == NULL )
      return 0;
   int nLeftHeight = find the left subtree height;
   int nRightHeight = find the right subtree height;
   
   // add one to the bigger of the two heights below us
   // and return it as our answer
   return 1 + max( nLeftHieght, nRightHeight );
}

In this code, though, how do we find the height of the subtrees below us? The answer is recursion; just call the GetTreeHeight() function passing in that sub tree and have ourselves figure out it again.

int GetTreeHeight( struct *pTree )
{
   if ( pTree == NULL )
      return 0;
   int nLeftHeight = GetTreeHeight( pTree->pLeft );
   int nRightHeight = GetTreeHeight( pTree->Right );
   
   // add one to the bigger of the two heights below us
   // and return it as our answer
   return 1 + max( nLeftHieght, nRightHeight );
}

We can step through this using the second mike and joe example above. We call the function with a pointer to "mike", the root node of the tree.

It sees that pTree isn't null, so we don't return zero. We take the pointer to the left sub tree, which points to "joe", and call ourselves again.

So we're back at the beginnig. pTree isn't null, it points at Joe. We again call GetTreeHeight(), but that's the base case; we're passing NULL, so we know it returns zero. Same for the right side. At this point, nLeftHeight = 0, and nRightHeight = 0.

The max of 0 and 0 is zero, and we add one to that, and return it ... we return 1.

We're back in the first instance of the function, then, with nLeftHeight = 1. We have to call GetTreeHeight() on pRight from the "mike" node, which is NULL and will return zero. Here, then, nLeftHeight = 1 and nRightHeight = 0.

The max of 1 and 0 is 1, and we add one to that, which is two. We return it.

The idea is to decompose the problem into simpler stuff. The height of an empty tree is zero. How is any non-zero tree different in height than the empty tree? Well, we don't know, becaue we don't know how many levels we have. We know it's one more than the rest of the levels, though, because we just consumed a level. So we add one to a function that figures out the levels of the deeper nodes. We can do that recursively as many times as we need to (or, at least, as many times as our stack space will allow.)

I hope that helps.

I feel bad that you had to spend time to write so much, but I reread it a few times and it seems like you are trying to explain recursion of the tree to me. I understand how recursion works, but the trouble I had with the assignment was trying to write a recursive method that has no parameters, my professor told me to use a private helper method but I dont understand how to do it.

 

[LuminaryJanitor]

...the trouble I had with the assignment was trying to write a recursive method that has no parameters, my professor told me to use a private helper method but I dont understand how to do it.

That part's pretty straightforward.

- Write your recursive method, with parameters.

- Write a second method which provides the initial argument for the recursive function.

So if your recursive function is getTreeHeight, as defined by mikeblas, your second function will simply be

int height()
{    return getTreeHeight(root); }

The user doesn't have direct access to the root, so they can't make this call themselves.