Recursive boolean function for a binary search tree

Question

I have a class implementing binary search tree and one of my private methods is method bool find(Node<Key, Info> * &node, Key _key);, where node stands for a pointer to a node, we start searching from and _key stands for a unique for every node key. My method is implemented as follows:

template<typename Key, typename Info>
bool BST<Key, Info>::find(Node<Key, Info>* &node, Key _key)
{
    if (node)
    {
        if (node->key == _key)
        {
            return true;
        }
        else
        {
            find(node->left, _key);
            find(node->right, _key);
            return false;
        }
    }
    else return false;
}

And it doesn't return true, even if the element with the given key exists. I added a printing command just before return statement and it executes so my function seems to find the given node, but I guess my understanding is wrong and it still somehow returns false.

Solved

The solution to my problem seems to be found :)

template<typename Key, typename Info>
bool BST<Key, Info>::find(Node<Key, Info>* &node, Key _key)
{
    if (node)
    {
        if (node->key == _key)
        {
            return true;
        }
        else if(_key<node->key)
            return find(node->left, _key);
        else 
            return find(node->right, _key);
    }
    else return false;
}

Why do you ignore the result of find in your else branch? Try to follow your code logically on some simple example. — Dan M.
– Dan M., Commented Nov 21, 2018 at 16:32
Please move your solution to an answer of its own, thank you. — Cœur
– Cœur, Commented Dec 31, 2018 at 7:46

Little Boy Blue · Accepted Answer · 2018-11-21 16:40:24Z

For binary search trees, you, of course, want to walk down the tree until you find the value or reach nullptr. I'll write out a search function real quick here:

bool search(Node * node, int value){
    if(node == nullptr) //If it's nullptr, we've reached the end without finding value.
        return false;
    if(node->value == value) //If it's value, we've found it!
        return true;
    if(node->value > value) //If value is less than node's value, go to left.
        return search(node->left, value);
    if(node->value < value) //If value is greater than node's value, go to right.
        return search(node->right, value);
}

This is a recursive search for an organized tree (without using templates, for the sake of simplicity). Therefore, in a binary search tree, you first need to check if node is nullptr, then if it is value, and then go from there.

Collectives™ on Stack Overflow

Recursive boolean function for a binary search tree

Solved

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

Solved

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related