CODEWITHSUNDEEP
c++
Zach_Cat
Zach_Cat

Reputation: 59

Search Binary Tree function not work c++

and I was trying to implement a binary searching tree:

template <typename T>
bool Tree<T>::search(TreeNode<T> *ptr, const T &key) {
if (ptr == 0) {
 cout<<"No such data: "<<key<<" in the tree"<<endl; 
 return false;
 }
else{
if (ptr->data == key) {
    cout<<"Find a node whose data is "<<key<<endl;
      return true;
} 
else if (ptr->data < key)  return search(ptr->leftPtr,key);

else  return search(ptr->rightPtr,key);
}
}

But the result always returns false no matter the tree contains the key value or not. Can u guys help me check the code? I tried debug, but still do not know.

Thank you!

Upvotes: 1

Views: 78

Answers (1)

WhozCraig
WhozCraig

Reputation: 66194

Your traversal comparator for left-tree descending is backwards. As such, as soon as you incorrectly descend into the right tree you stand no chance of ever finding that value. Only the root, and root only, will ever be found correctly.

This:

if (ptr->data < key)
    return search(ptr->leftPtr,key);
else
    return search(ptr->rightPtr,key);

Should read like this:

if (key < ptr->data) // <== note key is LESS THAN node.
    return search(ptr->leftPtr,key);
else
    return search(ptr->rightPtr,key);

That said, consider this:

template <typename T>
bool Tree<T>::search(TreeNode<T> *ptr, const T &key)
{
    if (ptr == 0) {
        cout<<"No such data: "<<key<<" in the tree"<<endl;
        return false;
    }

    if (key < ptr->data)
        return search(ptr->leftPtr, key);
    else if (ptr->data < key)
        return search(ptr->rightPtr, key);

    cout<<"Found a node whose data is "<< key << endl;
    return true;
}

Upvotes: 2

Related Questions