searching between min/max in a binary tree

[indiocolifa]

Suppose I need to search and count the number of items in a binary tree that fall between a range (min-Max). It's the following code correct?


void SearchTree ( TREE* treeptr, int min, int max, int* n)
{
if (treeptr != NULL)
{
if (treeptr->info <= max) && (treeptr->info >= min)
{
searchTree(&treeptr, min, max, (*n) + 1 );
searchTree(&treeptr, min, max, (*n) + 1 );
}
else if (treeptr->info > max) then searchTree(tree->left,min,max, &n)
else searchTree(tree->right, min, max, &n);
}
}


Thank you very much

[Yves M]

It's OK, but I don't see what you are trying to achieve with the variable n. If that is supposed to be the count, then it doesn't work.

[indiocolifa]

yes im trying N to be the count!

It's a syntax error (e.g pointer dereferencing,etc) or the use of N is not as it should be?

[Yves M]

Ok, if n is supposed to be the count, then it's quite wrong. One error is searchTree(tree->left,min,max, &n). n has the type int *, so &n has the type int **. So you can't pass that to your function, since the function expects an int *. If you want to keep the pointer, just pass it as plain n.

The other problem lies in the updating of the count. You should treat *n (i.e. the value that n points to) the same way as a global variable. This means that you just add one to it when the condition is true, and nothing when it's false.

Passing (*n) + 1 recursively is even worse than the passing &n. Now you are passing a value (an int) instead of a pointer to an int. Plus, only the recursive call would see the "n+1" value. That is not what you want, because after all the recursive calls have returned, you would still be stuck with the original value (i.e. 0).

Probably the simplest way to write this correctly would be to use a reference to an integer. Then you won't have to deal with the pointer syntax at all.

Finally, in C++ it's if (condition) { statements; }, not if (condition) then

I hope you read and understand this message, instead of just looking at the modified source ;)

void SearchTree ( TREE* treeptr, int min, int max, int &n)
{
if (treeptr != NULL)
{
if (treeptr->info <= max) && (treeptr->info >= min)
{
++n; // One value in the range, so increase the counter
searchTree(&treeptr, min, max, n);
searchTree(&treeptr, min, max, n);
}
else if (treeptr->info > max) {
searchTree(tree->left,min,max, n);
} else {
searchTree(tree->right, min, max, n);
}
}
}

[indiocolifa]

yes, the if..then problem was because I've looked to a Pascal source

thank you very much

[Yves M]

You're welcome ;) Yeah, I thought that the "then" was a copy/paste problem, but I just wanted to point it out. Sorry for being a bit dry and making it sound like your mistake ;)

[yuwaraj]

Hi Yuev M,

U wrote,

void SearchTree ( TREE* treeptr, int min, int max, int &n)
{
if (treeptr != NULL)
{
if (treeptr->info <= max) && (treeptr->info >= min)
{
++n; // One value in the range, so increase the counter

doubt here ========>

searchTree(&treeptr, min, max, n); <=============== ( 1 )
searchTree(&treeptr, min, max, n);
}
else if (treeptr->info > max) {
searchTree(tree->left,min,max, n);
} else {
searchTree(tree->right, min, max, n);
}
}
}

But here i didn't understant let's consider following tree,

23
/ \
12 46
/ \ / \
2 13 22 48

If i have min=11 max=48 and my ptr points to node 12
which is between min and max now according to ur code 'n' will be increased (that's write)
but now i should make a call on left and right of '12' i.e. searchTree( 12->left, min, max, n)
and searchTree( 12->right , min, max, n) (is it correct ?). so that programe proceed further.

If it is doing it already then what trick is been made, please let me know .


thanx

[indiocolifa]

yes you're right, the correct code is


void SearchTree ( TREE* treeptr, int min, int max, int &n)
{
if (treeptr != NULL)
{
if (treeptr->info <= max) && (treeptr->info >= min)
{
++n; // One value in the range, so increase the counter
searchTree(&treeptr->left, min, max, n);
searchTree(&treeptr->right, min, max, n);
}
else if (treeptr->info > max) {
searchTree(tree->left,min,max, n);
} else {
searchTree(tree->right, min, max, n);
}
}
}


good observation! :thumb:

[Yves M]

Correct, and replace the "tree" by "treeptr" at the bottom of the code. I hadn't even checked whether that was correct or not ;)

[indiocolifa]

Now, following with this talking about binary search trees, suppose I defined the following tree:


struct tree {
int data1,data2;
tree* left;
tree* right;
} * TREE;



data is ordered by data1 in this tree, but I need to extract the maximum data2 element, so I need to traverse the entire tree.

My code is as follows:


void findData2Max (TREE* t, int& max)
{
if (t != NULL)
{
if (t->data2 > max) max = t->data2;
findData2Max (t->left, max);
findData2Max (t->right,max);
}
}


It is that code correct? ( supposing we call findData2Max with the maximum set to, e.g, zero )

thank you very much

[Yves M]

yeah, that's OK, but as you noticed it's not very efficient.

[indiocolifa]

Correct me if I'm wrong, but this is a binary search tree and this is the only manner to search for a maximum for a non-primary key.