C++ Binary Search Tree Recursive search function

Question

template <class T>
bool BST<T>::search(const T& x, int& len) const
{
    return search(BT<T>::root, x);
}


template <class T>
bool BST<T>::search(struct Node<T>*& root, const T& x)
{
   if (root == NULL)
    return false;
   else
      {
      if (root->data == x)
    return true;
   else if(root->data < x)
    search(root->left, x);
   else 
    search(root->right, x);

   } 

}

So this is my search function for my BST class with a T node. x is the data being searched for within the tree, len is just the amount of nodes it has to travel to come up with the matching node if it exists. I have not implented that yet, I'm just incrementally developing my assignment. I'm calling it by doing this:

if(t.search(v[1], len) == true)
    cout << endl << "true";

v is just a vector I had to create to compare it to, and so this is just supplying it with an int. The error I'm getting:

BST.h: In member function âbool BST::search(const T&, int&) const [with T = int]â: prog5.cc:24: instantiated from here

BST.h:78: error: no matching function for call to âBST::search(Node* const&, const int&) constâ

BST.h:76: note: candidates are: bool BST::search(const T&, int&) const [with T = int]

BST.h:83: note: bool BST::search(Node*&, const T&) [with T = int]

So I'm not sure what I'm doing wrong or where I'm doing wrong. Probably something silly and small :\

Answer 1

Okay, bool BST<T>::search(struct Node<T>*& root, const T& x) should probably have const after it like so: bool BST<T>::search(struct Node<T>*& root, const T& x) const. Basically, you've called a non-const function from a const function and this is a no-no.

BTW, this looks suspect to me "struct Node<T>*&"... I'd probably drop the & and work with Node<T>*... but maybe you need that because of the struct?

Also, this is C++, there is no reason to leave Node as a struct... needing to have struct in the parameter definition just looks bad, IMHO. Why not make Node a class?