Insertion error in Binary Search tree

1
votes
void BST::insert(string word)
{
   insert(buildWord(word),root);
}
  //Above is the gateway insertion function that calls the function below
  //in order to build the Node, then passes the Node into the insert function
  //below that

Node* BST::buildWord(string word)
{
   Node* newWord = new Node;
   newWord->left = NULL;
   newWord->right = NULL;
   newWord->word = normalizeString(word);

   return newWord;
}
   //The normalizeString() returns a lowercase string, no problems there

void BST::insert(Node* newWord,Node* wordPntr)
{
  if(wordPntr == NULL)
  {
  cout << "wordPntr is NULL" << endl;
  wordPntr = newWord;
  cout << wordPntr->word << endl;
  }
  else if(newWord->word.compare(wordPntr->word) < 0)
  {
     cout << "word alphabetized before" << endl;
     insert(newWord,wordPntr->left);
  }
  else if(newWord->word.compare(wordPntr->word) > 0)
  {
     cout << "word alphabetized after" << endl;
     insert(newWord, wordPntr->right);
  }
  else
  {
     delete newWord;
  }
}

So my problem is this: I call the gateway insert() externally (also no problems with the inflow of data) and every time it tells me that the root, or the initial Node* is NULL. But that should only be the case before the first insert. Each time the function is called, it sticks the newWord right at the root. To clarify: These functions are part of the BST class, and root is a Node* and a private member of BST.h

It's possible it is quite obvious, and I have just been staring too long. Any help would be appreciated. Also, this is a school-assigned project.

Best

2
c++recursionbinary-search-tree
How are you initializing the root node? - jrad
The root Node is initialized to NULL in the constructor: - Zeke
BST::BST() { chooseRight = true; root = NULL; } - Zeke
And is root ever pointed to anything except NULL? - jrad
The Only time it is pointed to NULL is when the constructor is called implicitly via instantiation of the BST class, which happens only once. @JackRadcliffe - Zeke

2 Answers

0
votes

The assignment wordPntr = newWord; is local to the insert function, it should somehow set the root of the tree in this case.

0
votes

Like user946850 says, the variable wordPntr is a local variable, if you change it to point to something else it will not be reflected in the calling function.

There are two ways of fixing this:

  1. The old C way, by using a pointer to a pointer:

    void BST::insert(Node *newWord, Node **wordPntr)
{
    // ...
    *wordPntr = newWord;
    // ...
}

    You call it this way:

    some_object.insert(newWord, &rootPntr);

  2. Using C++ references:

    void BST::insert(Node *newWord, Node *&wordPntr)
{
    // Nothing here or in the caller changes
    // ...
}

To help you understand this better, I suggest you read more about scope and lifetime of variables.