CODEWITHSUNDEEP
c++recursiontreebinary-tree
Alex
Alex

Reputation: 2289

Recursive search on binary tree returning both true and false

For an assignment I'm supposed to come up with a recursive function called all_less which takes in a a pointer to any arbitrary tree (TN<T>*) and a T parameter. It returns true if all the values are less than the T parameter, otherwise it returns false.

The instance variables for my Tree class are this:

T      value;
TN<T>* left;
TN<T>* right;

And the function prototype for all_less looks like this:

template<class T>
bool all_less(TN<T>* t, T v)

Since I have to consider an unsorted binary tree, I figured recursively going down each subtree and checking each value would work ok. After testing out this function:

template<class T>
bool all_less(TN<T>* t, T v)
{
    if(v <= t->value) {
        return false;
    } else if(v > t->value) {
        if(t->right != nullptr && t->left != nullptr) {
            all_less(t->right, v);
            all_less(t->left, v);
        }
    }
    return true;
}

After having some issues with the function almost always returning true, I put some print statements before return true and return false to see what was happening.

As an example, lets say that we have the values 12, 15, 14, 5, in the binary tree. Running my function with using:

TN<int>* t;
std::cout << all_less(t, 15);

as input, would output this:

true
false
true
true

The end result would end up true, even though a false was returned once. How do I get it so that if it returns false, the function returns false and stops immediately? Also is there a better way to go about implementing this function? I did originally have a couple extra if-else statements to check if the right/left subtrees were null and go on from there, but those didn't seem to actually do anything.

Upvotes: 1

Views: 984

Answers (2)

molbdnilo
molbdnilo

Reputation: 66371

You're ignoring the return values of the recursive calls.

The end result would end up true, even though a false was returned once.

That false was returned from a different function call and has disappeared into the great bitbucket in the sky.

Recursive functions work exactly like any other functions - if you have

int f() { return 0:}
int g(int x) { 
    if (x == 0) 
        f(); 
    return 1; 
}

g(0) will return 1, even though 0 was "returned once".
If g(0) should return f()'s value, it must do it explicitly:

int g(int x) { 
    if (x == 0) 
        return f(); 
    return 1; 
}

You're also assuming that all nodes have either zero or two children.

If you adopt the convention that all items in an empty tree are smaller than the value, you can write

template<class T>
bool all_less(TN<T>* t, T v)
{
    return !t
         || (  t->value < v
            && all_less(t->right, v)
            && all_less(t->left, v));
}

Upvotes: 3

R Sahu
R Sahu

Reputation: 206567

Your function:

template<class T>
bool all_less(TN<T>* t, T v)
{
    if(v <= t->value) {
        return false;
    } else if(v > t->value) { // Why do you need this check?
        if(t->right != nullptr && t->left != nullptr) {
            // This is wrong because it's possible for one them to
            // nullptr while the other is not.

            all_less(t->right, v);
            all_less(t->left, v);
            // The above function calls are no op. You are calling
            // the function recursively but are ignoring the return
            // values.
        }
    }
    return true;
}

This should work:

template<class T>
bool all_less(TN<T>* t, T v)
{
   if(v <= t->value) {
      return false;
   }

   if(t->right != nullptr )
   {
      if ( !all_less(t->right, v) )
      {
         return false;
      }
   }

   if ( t->left != nullptr)
   {
      if ( !all_less(t->left, v) )
      {
         return false;
      }
   }
   return true;
}

p.s. Untested code.

Upvotes: 0

Related Questions