So I have this code that I wrote that pretty much makes a binary search tree with one node per element that holds the data int, one pointer for left, and one pointer for right. My tree is set that if you give it a number it starts as root, then afterwards any number you give it will either be placed left or right if it smaller than the current node or bigger respectively until it hits a pointer that points to NULL.
I was able to get my code to display the numbers in order no matter how bad you inserted the numbers to throw me off. My question now is this, how can I make it count how many levels there are? I'm not sure if this is clear or unclear but I want it to take all the paths and return to me the longest path and that should be how many levels there are. Any ideas how I can do this? Thank you.
The best I can think of is a recursive function that tests every path, something like this:
1 2 3 4 5 6 7 8 9 10 11 12 13
int getHeight (node * r)
{
// Max is the greatest height below (*r), temp is just used to avoid calling getHeight(r->right) twice
int max=0,temp=0;
// Recurse down lhs
if (r->left!=NULL) max=getHeight(r->left);
// Recurse down rhs
if (r->right!=NULL) temp=getHeight(r->right);
if (temp>max) max=temp;
// Return 1 more than max
return max+1;
}
I tried taking a good hard look at it and it seems to me that it will always return an erroneous number cause doesn't max and temp get reset everytime you call it producing a 1 or 2 everytime? I'm not sure, right now I'm currently tired. Correct me if I'm wrong, which I probably am. lol
@theranga the problem is max and temp are getting reinitialized each recursion. I believe Skynet is correct, it's not likely going to produce a correct result because of that.
my algorithm pretty obviously does exactly the same thing as yours, so that bit's fine.
max and temp are local to that particular instance of the function, so they are not reinitialised every recursion. If they were global variables, that would be a problem, but they aren't, so there isn't an issue.