Рекурсивная логическая функция для бинарного дерева поиска

Question

У меня есть класс, реализующий двоичное дерево поиска, и один из моих частных методов - это метод bool find(Node<Key, Info> * &node, Key _key);, где node обозначает указатель на узел, с которого мы начинаем поиск, а _key обозначает уникальный для каждого узла.ключ.Мой метод реализован следующим образом:

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;
}

И он не возвращает true, даже если элемент с данным ключом существует.Я добавил команду печати непосредственно перед оператором return, и она выполняется так, что моя функция, кажется, находит данный узел, но я думаю, что мое понимание неверно, и оно все равно каким-то образом возвращает false.

---

Решено

Кажется, решение моей проблемы найдено:)

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;
}

Answer 1

Для бинарных поисковых деревьев вы, конечно, хотите пройтись по дереву, пока не найдете значение или не достигнете nullptr.Я очень быстро напишу здесь функцию поиска:

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);
}

Это рекурсивный поиск организованного дерева (для простоты без использования шаблонов).Поэтому в двоичном дереве поиска сначала необходимо проверить, является ли узел nullptr, затем - value, а затем перейти оттуда.