Start New Discussion within our Software Development Community

Can anyone tell me why my recursive find function for a binary search tree isn't working? It keeps returning false when searching for items that are in the tree. Thanks.

template<class T>
bool BST<T>::find(const T& sitem) const{
  //Precondition:
  //  A binary search tree exists
  //
  //Postcondition:
  //  If item is in the BST, true is returned, else false is returned
  //  A BST exists

  return find_R(sitem, root);
}


template<class T>
bool BST<T>::find_R(const T& sItem, TreeNode<T> *node) const{
  //Recursive function used by find
  //Precondition:
  //  A binary search tree exists
  //
  //Postcondition:
  //  If the search item is found, true is returned, else false is returned
  //  A BST exists

  if (node == NULL)
    return false;
  
  else if (node->item == sItem)
    return true;

  else if (node->item < sItem)
    return find_R(sItem, node->left);

  else if (node->item > sItem)
    return find_R(sItem, node->right);
}

I found the problem. The conditions of the if statements on lines 30 and 33 of find_R were wrong.
Should be

else if (sItem < node->item)
    return find_R(sItem, node->left);

  else if (sItem > node->item)
    return find_R(sItem, node->right);

Another case of not seeing the forest for the trees.

This question has already been answered. Start a new discussion instead.