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<T>::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<int>::search(Node<int>* const&, const int&) constâ    
BST.h:76: note: candidates are: bool BST<T>::search(const T&, int&) const [with T = int]
BST.h:83: note:                 bool BST<T>::search(Node<T>*&, const T&) [with T = int]

So I'm not sure what I'm doing wrong or where I'm doing wrong.

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?

Answer 2

There are multiple problems in your search code:

• The sort order is backwards, if the node data is less than what you search, you should search in the right branch, not the left branch.

• You should return the result of the recursive call

• It is also unclear why you pass root by reference. it should instead be passed as a const qualified pointer and the method body should be const qualified too.

Here is a alternative:

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

And here is a simpler non recursive implementation:

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

Answer 3

Algorithm :

1. Take node value data;
2. Repeat step 3 to step 5 until we find the value or we go beyond the tree.
3. If data is equal to root node value , searching is successful and terminate the algorithm.
4. If data is less than root node value , we have to search the left sub tree.
5. Else data is less than root node value , we have to search the left sub tree.
6. Output Print message "Found" or "Not Found".

---

C++ implementation

    node* search(node* root, int data)
    {
     if (root==NULL || root->data==data) return root;

     if (root->data < data)   return search(root->right, data);

     return search(root->left, data);
   }