little recursion question

Nov 16, 2015 at 3:35pm
I am a beginner. I have given myself a little recursion exercise. I have a binary search tree. I want to write a function that tells me if a particular value is in the tree.

So far, my function tells me if the value is present. But it fails if the value is not present.

1
2
3
4
5
6
7
8
9
bool Search_Tree(node * ptr_to_tree, int number) {
   if (ptr_to_tree->i == number)
      return true;

   if (ptr_to_tree->i <= number)
      Search_Tree(ptr_to_tree -> ptr_to_left, number);
   else
      Search_Tree(ptr_to_tree -> ptr_to_left, number);
}


I just can't see where to put
 
return false;

Can someone point that out to me?
Nov 16, 2015 at 3:38pm
If your pointer is NULL --> FALSE
Nov 16, 2015 at 4:09pm
OK, my code now looks like this
1
2
3
4
5
6
7
8
9
10
11
bool Search_Tree(node * ptr_to_tree, int number) {
   if (ptr_to_tree == 0)
      return false;
   if (ptr_to_tree->i == number)
      return true;

   if (number <= ptr_to_tree->i)
      Search_Tree(ptr_to_tree -> ptr_to_left, number);
   else if (number > ptr_to_tree->i)
      Search_Tree(ptr_to_tree -> ptr_to_right, number);
}

And behaves as expected.
But at compile time, I get a warning (not all control paths return a value). How can I resolve that warning?
Nov 16, 2015 at 5:37pm
If the function calls itself recursively, the value returned should be used in some way. I've not analysed this code in detail, and my code may be incorrect, but it seems that it might look something like this:

1
2
3
4
5
6
7
8
9
10
11
bool Search_Tree(node * ptr_to_tree, int number) {
   if (ptr_to_tree == 0)
      return false;
   if (ptr_to_tree->i == number)
      return true;

   if (number <= ptr_to_tree->i)
      return Search_Tree(ptr_to_tree -> ptr_to_left, number);
   else  // note "else if" changed to "else"
      return Search_Tree(ptr_to_tree -> ptr_to_right, number);
}
Nov 16, 2015 at 7:34pm
OK, that was a good suggestion and the warning is now gone.
Can we look at another procedure that is confusing me?

Show_Tree just displays the values in all nodes in the tree.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void Show_Tree(node * ptr_to_tree) {
  /*
   if (ptr_to_tree == 0) {
      printf("The tree is empty.\n\n");
      return;
   }
   */
   
   if (ptr_to_tree == 0)
      return;
   
   Show_Tree(ptr_to_tree -> ptr_to_left);
   printf("%d\n", ptr_to_tree -> i);
   Show_Tree(ptr_to_tree -> ptr_to_right);   
}

The following code is necessary:
1
2
if (ptr_to_tree == 0)
   return;

But then I thought it would be nice to display a message if the tree is empty. So, I replaced that code with:
1
2
3
4
if (ptr_to_tree == 0) {
   printf("The tree is empty.\n\n");
   return;
}

But if the tree is not empty, the results are different and not good. (Displays "The tree is empty." before each value. ugh.) If the tree is empty, the message displays just fine.
Assuming that it is possible to display a 'tree is empty' message if the tree is empty, and then stop all processing in the procedure, how would I do that?
Last edited on Nov 16, 2015 at 8:22pm
Topic archived. No new replies allowed.