Issues with recursive bool function

Question

bool search(double x, TreeNode *t)
{
    if (t->value == x)
        return true;
    else if (x < t->value)
        search(x, t->left);
    else if (x > t->value)
        search(x, t->right);
    return false;

bool search(double num)
{
    TreeNode *ptr = root;
    return search(num, ptr);
}

The search function with 2 arguments is a private member function of a binary tree class that uses recursion to search for a value. The other search function is called to call the recursive function. This code does not work. I have displayed the value of the recursive function and it does not return 0 or 1. I have no idea why. Also, if I send in a value that is not in the tree, the program crashes so I get no errors to help me.

`search(x, t->left);` - don't you mean `return search(x, t->left);`? — Jesper Juhl, Apr 15 '18 at 17:31
first of all function return bool, which is true value and not 1/0, there is no nullptr check, there is no return on the recursion call. — Arkady Godlin, Apr 15 '18 at 17:33
A `double` and a `==` do not mix. https://stackoverflow.com/questions/588004/is-floating-point-math-broken — Yunnosch, Apr 15 '18 at 17:33

score 1 · Accepted Answer · answered Apr 15 '18 at 18:55

Your recursion never stops if you don't find an element.
If it's found in the root, you return true.
If it's found somewhere else, you return false.

You need to

Handle the empty tree, and
Return something meaningful when recursing.

Like

bool search(double x, const TreeNode *t)
{
    if (t == nullptr)
        return false;
    else if (t->value == x)
        return true;
    else if (x < t->value)
        return search(x, t->left);
    else
        return search(x, t->right);
}

or

bool search(double x, const TreeNode *t)
{
    return t != nullptr
          && (  t->value == x
            || (t->value < x && search(x, t->left))
            || (t->value > x && search(x, t->right)));
}

This works. Thank you very much. I didn't even think to use return when calling recursion. — Tom Eggleston, Apr 16 '18 at 01:44

Issues with recursive bool function

1 Answers1