"contains" function for BST

[MikeCheezy]

Hello everyone, I was practicing implementing BSTs from scratch and wrote a "contains" function. The function basically takes in a value and the root and returns true or false when the value is found/not found.

However, when I run it, I'm running into an issue where it says "Problem.cpp(44) : error C2664: 'bool BinarySearchTree::contains(const Node &,int)' : cannot convert argument 1 from 'Node *' to 'const Node &'
Reason: cannot convert from 'Node *' to 'const Node' "

I'm assuming the issue is root.getLeft() and root.getRight() returns a Node * format instead of a const Node.

How would I convert Node * to the const Node format required for my function?

Thank you.

 #include <stdexcept>
#include <string>
#include <iostream>

class Node
{
public:
    Node(int value, Node* left, Node* right)
    {
        this->value = value;
        this->left = left;
        this->right = right;
    }

    int getValue() const
    {
        return value;
    }

    Node* getLeft() const
    {
        return left;
    }

    Node* getRight() const
    {
        return right;
    }

private:
    int value;
    Node* left;
    Node* right;
};

class BinarySearchTree
{
public:
    static bool contains(const Node& root, int value)
    {
        if (root.getValue() == NULL) return false;
        else {
            if (root.getValue() == value) return true;
            else if (value > root.getValue()) contains(root.getRight(), value);
            else if (value < root.getValue()) contains(root.getLeft(), value);
        }
    }
};

#ifndef RunTests
int main()
{
    Node n1(1, NULL, NULL);
    Node n3(3, NULL, NULL);
    Node n2(2, &n1, &n3);

    std::cout << BinarySearchTree::contains(n2, 3);
}
#endif 

[mbozzi]

Change lines 44 and 45 to dereference the right and left sides of the root node.
You need to make sure that those pointers are not null before they are dereferenced.

[MikeCheezy]

@mbozzi:

Thank you! Just dereferenced the right and left sides and it ended up working.

            else if (value > root.getValue()) {
                if (root.getRight() != NULL) {
                    contains(*root.getRight(), value);
                }
                
            }
            else if (value < root.getValue()) {
                if (root.getLeft() != NULL) {
                    contains(*root.getLeft(), value);
                }
            }