request for your comments on a Tree Search function

[smoking81]

hello there!
i'd kindly like to ask your comments about this function.
The assignment is to write a function which searches for a given key in a binary tree and returns 1 if the key is found, 0 if not. The function should stop searching if the key is met.

I wrote this:

int searchTree (NodePtr headPtr,int key)
{
	if (headPtr==NULL)
	{
		return 0;
	}
	else
	{
		if (headPtr->value==key)
		{
			return 1;
		}
		else
			if (search (headPtr->leftPtr,key))
			{
				return 1;
			}
			else
			{	
				if (search (headPtr->rightPtr,key))
				{
					return 1;
				}
				else
				{
					return 0;
				}
			}
	}
}

I used the several IF to have clearer what happens (i still have some problems with recursion).. According to you, is this function formally a good solution to the given problem?
many thanks (once again! )

[Prelude]

I'm guessing about how search works, but won't this work?

int searchTree (NodePtr headPtr,int key)
{
  if (headPtr==NULL)
  {
    return 0;
  }
  else
  {
    return search (headPtr, key);
  }
}

Or, assuming search takes into account the first argument being null:

int searchTree (NodePtr headPtr,int key)
{
  return search (headPtr, key);
}

In which case, why even have searchTree?

[smoking81]

I'm guessing about how search works, but won't this work?

int searchTree (NodePtr headPtr,int key)
{
  if (headPtr==NULL)
  {
    return 0;
  }
  else
  {
    return search (headPtr, key);
  }
}

Or, assuming search takes into account the first argument being null:

int searchTree (NodePtr headPtr,int key)
{
  return search (headPtr, key);
}

In which case, why even have searchTree?

sorry.. i meant it recursive.. It shall be a set of recursive calls to searchTree, there is no search function..

[Prelude]

I usually default to something like this:

int search ( node *root, int key )
{
  if ( root != NULL ) {
    if ( key == root->data )
      return 1;
    else if ( key < root->data )
      return search ( root->left, key );
    else /* key > root->data */
      return search ( root->right, key );
  }

  return 0;
}

[iMalc]

Well that's certainly tidy indentation, but you don't need to indent the code like that in this case. It is probably better to structure it like this:

int searchTree(NodePtr headPtr, int key)
{
	if (headPtr == NULL)
	{
		return 0;
	}
	else if (headPtr->value == key)
	{
		return 1;
	}
	else if (searchTree(headPtr->leftPtr, key))
	{
		return 1;
	}
	else if (searchTree(headPtr->rightPtr, key))
	{
		return 1;
	}
	else
	{
		return 0;
	}
}

The last part could be outside an else instead too.

The next question then is: Is this an 'ordered' binary search tree?
If so, there's no need to search more than one branch in any case. You simply check which branch the item would be in and only search that one.
Prelude shows a good way to do that.

I would actually write it non-recursively myself, assuming that it is also perfectly okay for your asignment.

[smoking81]

The next question then is: Is this an 'ordered' binary search tree?
If so, there's no need to search more than one branch in any case. You simply check which branch the item would be in and only search that one.
Prelude shows a good way to do that.

I would actually write it non-recursively myself, assuming that it is also perfectly okay for your asignment.

The tree is not specified to be a search tree otherwise of course it could be done according to Prelude's code..
how would you write it iteratively? Isn't it more complicated for trees?

[dwks]

Not really.

int search(node *root, int key) {
    while(root) {
        if(key == root->data) return 1;

        if(key < root->data) root = root->left;
        else root = root->right;
    }

    return 0;
}

Searching is quite simple, because you only follow one path. If you wanted to access every node of the tree iteratively, it would be more complicated.

[iMalc]

The tree is not specified to be a search tree otherwise of course it could be done according to Prelude's code..
how would you write it iteratively? Isn't it more complicated for trees?

I don't know why you're saying "search tree". Trees are for looking up items, not just for looking pretty . I was asking if it was "ordered".
In other words, does it maintain the property that no leftPtr values are ever greater than their parent node, and no rightPtr values are ever less than their parent node?

If not, why not, and what is the point of the tree then?

If yes, then dwks has just shown how we do it iteratively. It's no harder at all.

[Sebastiani]

>> Well that's certainly tidy indentation, but you don't need to indent the code like that in this case. It is probably better to structure it like this:

what does style have to do with it anyway? Prelude's example was correct. your version does the exact same thing. just not as eloquently.

[iMalc]

>> Well that's certainly tidy indentation, but you don't need to indent the code like that in this case. It is probably better to structure it like this:

what does style have to do with it anyway? Prelude's example was correct. your version does the exact same thing. just not as eloquently.

Sorry, I would have thought it was obvious that I was responding to the original post.

[smoking81]

I don't know why you're saying "search tree". Trees are for looking up items, not just for looking pretty . I was asking if it was "ordered".
In other words, does it maintain the property that no leftPtr values are ever greater than their parent node, and no rightPtr values are ever less than their parent node?

If not, why not, and what is the point of the tree then?

If yes, then dwks has just shown how we do it iteratively. It's no harder at all.

i thought the name of trees with the properties you specified are called "binary search trees"..
anyway, in the text of the exercise they don't specify this property so i think it should be thought as a randomly initialized tree..

[Sebastiani]

>> Sorry, I would have thought it was obvious that I was responding to the original post.

ah, right.