simple binary search tree in C++.. HELP WITH FIND

[gekko3558]

I am writing a simple binary search tree (nodes are int nodes) with a BSTNode class and a BST class. I have followed the instructions from my C++ book, and now I am trying to get a remove method working. But before I get to the remove, I need to get my find method working. Basically, I am trying to get a "find" method working that will search for a giving int value, and return the node with that value. I have designed my current find with the help of my book, but for some off reason, when I run my program and try to find the values I do, it returns "10" (the root) everytime, and will not complete when I try to find a number thats not in the tree. Any help would be great!

#include <iostream>
using std::cout;
using std::endl;
 
class BSTNode
{
 friend class BST;
  public:
   BSTNode(int); 
   int getValue();
    void print();
 
  private:
   int value;
   BSTNode *leftPtr;
   BSTNode *rightPtr;
};
 
class BST
{
 public:
   BST();
   void insertNode(const int &);
    BSTNode find(const int);
 
 private:
   BSTNode *rootPtr;
 
   void insertNodeHelper(BSTNode**, const int &);
    BSTNode findHelper(BSTNode**, const int);
};
 
/****
 MAIN
*****/
int main(void)
{
   cout << "TESTING MY BSTNode CLASS:" << endl
       << "creating nodes with values 3, 4, and 5" << endl << endl;
    BSTNode node1 = BSTNode(3);
    cout << "node1 has value of: " << node1.getValue() << endl;
    BSTNode node2 = BSTNode(4);
    cout << "node2 has value of: " << node2.getValue() << endl;
    BSTNode node3 = BSTNode(5);
    cout << "node3 has value of: " << node3.getValue() << endl;
 
    cout << endl << "Using the print method, the values are:" << endl;
    node1.print();
    node2.print();
    node3.print();
 
    cout << endl << endl << "TESTING MY BST CLASS:" << endl
       << "adding 10, 5, 15, 20, 8, and 10 to the tree" << endl;
    //Binary Search Tree
    BST tree = BST();
    tree.insertNode(10);
    tree.insertNode(5);
    tree.insertNode(15);
    tree.insertNode(20);
    tree.insertNode(8);
    tree.insertNode(10);
 
    cout << endl << "testing the find method" << endl;
    cout << tree.find(10).getValue() << " ";
    tree.find(5).print();
    tree.find(15).print();
    tree.find(20).print();
 
    return 0;
}
 
/***************
 BSTNode Methods
****************/
 
//CONSTRUCTOR
BSTNode::BSTNode(int d)
   : value(d),
     leftPtr(NULL),
     rightPtr(NULL)
   {}
 
//METHODS
int BSTNode::getValue()
   {return value;}
void BSTNode::print()
   {cout << value << " ";}
 
/***********
 BST Methods
************/
 
//CONSTRUCTOR
BST::BST() 
   {rootPtr = NULL;}
 
//INSERT METHOD
void BST::insertNode(const int &value)
   {insertNodeHelper(&rootPtr, value);}
void BST::insertNodeHelper(BSTNode **ptr, const int &value)
{
   if (*ptr == NULL)  
      *ptr = new BSTNode(value);
   else
   {     
      if (value < (*ptr)->value)
         insertNodeHelper(&((*ptr)->leftPtr), value);
      else
      {
 
         if (value > (*ptr)->value)
            insertNodeHelper(&((*ptr)->rightPtr), value);
         else  //SKIPS DUPLICATE NUMBERS
            cout << "   " << value << " already exists in the tree... no duplicates will be added" << endl;
      }
   }
}
 
//FIND METHOD FOR USE WITH REMOVE
BSTNode BST::find(const int value)
   {return findHelper(&rootPtr, value);}
BSTNode BST::findHelper(BSTNode **ptr, const int value)
{
   if (value == (*ptr)->value)
       return **ptr;
    else
    {
       if ((*ptr)->value > value)
          findHelper(&((*ptr)->leftPtr), value);
 
       else
        {
           if ((*ptr)->value < value)
             findHelper(&((*ptr)->rightPtr), value);
 
          else
             {cout << "node not found"; return BSTNode(-1);}
        }
    }
}
 

[Ganon11]

Try using (*ptr)->getValue() rather than (*ptr)->value. I suspect this is messing things up.

[gekko3558]

Try using (*ptr)->getValue() rather than (*ptr)->value. I suspect this is messing things up.

that is a very great idea, however it did not change the output. Any other suggestions?

[Ganon11]

Ah-hah!

In your first condition, if the value you're searching for is the root's value, then you return the root. But look at your next two conditions. If the value is less, then you call findHelper again - but you don't return the value! The only case where you return something is if the root is the search value or if the search value doesn't exist in the tree. Change these findHelper calls to return findHelper and see if it works.

[gekko3558]

Ah-hah!

In your first condition, if the value you're searching for is the root's value, then you return the root. But look at your next two conditions. If the value is less, then you call findHelper again - but you don't return the value! The only case where you return something is if the root is the search value or if the search value doesn't exist in the tree. Change these findHelper calls to return findHelper and see if it works.

HAHA, yeah i actually JUST noticed this right before I read this comment. Dumbest mistake ever lol. But I did this, the find works great... EXCEPT when the value i search for is not found... The problem now seems in returning a NULL pointer im guessing, perhaps I'm making another stupid mistake. I have changed my entire code to as follows:

#include <iostream>
using std::cout;
using std::endl;
 
class BSTNode
{
 friend class BST;
  public:
   BSTNode(int); 
   int getValue();
    void print();
 
  private:
   int value;
   BSTNode *leftPtr;
   BSTNode *rightPtr;
};
 
class BST
{
  public:
   BST();
   void insertNode(const int &);
    BSTNode* find(const int &);
 
  private:
   BSTNode *rootPtr;
 
   void insertNodeHelper(BSTNode**, const int &);
    BSTNode* findHelper(BSTNode*, const int &);
};
 
/****
 MAIN
*****/
int main(void)
{
   cout << "TESTING MY BSTNode CLASS:" << endl
       << "creating nodes with values 3, 4, and 5" << endl << endl;
    BSTNode node1 = BSTNode(3);
    cout << "node1 has value of: " << node1.getValue() << endl;
    BSTNode node2 = BSTNode(4);
    cout << "node2 has value of: " << node2.getValue() << endl;
    BSTNode node3 = BSTNode(5);
    cout << "node3 has value of: " << node3.getValue() << endl;
 
    cout << endl << "Using the print method, the values are:" << endl;
    node1.print();
    node2.print();
    node3.print();
 
    cout << endl << endl << "TESTING MY BST CLASS:" << endl
       << "adding 3, 2, 5, 1, 4, 6, and 4 to the tree" << endl;
    //Binary Search Tree
    BST tree = BST();
    tree.insertNode(3);
    tree.insertNode(2);
    tree.insertNode(5);
    tree.insertNode(1);
    tree.insertNode(4);
    tree.insertNode(6);
    tree.insertNode(4);
 
    cout << endl << "testing the find method" << endl;
    for(int i = 1; i <= 6; i++)
    {
       if(tree.find(i) == NULL)
           cout << i << " was not found!" << endl;
       else
           (tree.find(i))->print();
    }
 
    return 0;
}
 
/***************
 BSTNode Methods
****************/
 
//CONSTRUCTOR
BSTNode::BSTNode(int d)
   : value(d),
     leftPtr(NULL),
     rightPtr(NULL)
   {}
 
//METHODS
int BSTNode::getValue()
   {return value;}
void BSTNode::print()
   {cout << value << " ";}
 
/***********
 BST Methods
************/
 
//CONSTRUCTOR
BST::BST() 
   {rootPtr = NULL;}
 
//INSERT METHOD
void BST::insertNode(const int &value)
   {insertNodeHelper(&rootPtr, value);}
void BST::insertNodeHelper(BSTNode **ptr, const int &value)
{
   if (*ptr == NULL)  
      *ptr = new BSTNode(value);
   else
   {     
      if (value < (*ptr)->getValue())
         insertNodeHelper(&((*ptr)->leftPtr), value);
      else
      {
 
         if (value > (*ptr)->getValue())
            insertNodeHelper(&((*ptr)->rightPtr), value);
         else  //SKIPS DUPLICATE NUMBERS
            cout << "   " << value << " already exists in the tree... no duplicates will be added" << endl;
      }
   }
}
 
//BEGINNING OF REMOVE
//FIND METHOD FOR USE WITH REMOVE
BSTNode* BST::find(const int &value)
   {return findHelper(rootPtr, value);}
BSTNode* BST::findHelper(BSTNode *ptr, const int &value)
{
   while (ptr!=NULL || (ptr)->getValue() == value)
   {
      if ((ptr)->getValue() > value)
         ptr = (ptr)->leftPtr;
      else if ((ptr)->getValue() < value)
         ptr = (ptr)->rightPtr;
      else if ((ptr)->getValue() == value)
         break;
   }
 
   if (!ptr)
       return NULL;
   else
      return ptr;
}
 

[gekko3558]

nevermind!!!! I figured it out, thanks so much for you help though..

instead of checking

if(!tree.find(value))
{
   not found code
}
else
{
   found code
}
 

i needed to do it this way

if(tree.find(value))
{
   found code
}
else
{
   not found code
}