How to add children to BST

Question

I'm trying to make/create a BST, but it doesn't seem to work properly. I've literally been sitting here for hours trying to figure out what's going on. It's gotten to the point where I've drawn a million diagrams to figure this out, yet my code fails me. I need to pass in a root node into a function. Then I need to traverse through the tree until I find that the parent string parameter of the function coincides with the tree parent node's string. If I do find it, I must insert the string into the parent, and create two new children from that parent. If I can't find the parent string, then I return false.

 bool insertNode(BSTNode *n, char* parentQ, char* leftQ, char* rightQ)
 {   
  if(n->Q == parentQ)
  {
    n->left = new BSTNode(leftQ);
    n->right = new BSTNode(rightQ);
    return true;
  }
  else if(n->Q != parent)
  {
    insertNode(n->left,parentQ,leftQ,rightQ);
    insertNode(n->right,parentQ,leftQ,rightQ);
  }
  else
    return false;
}

Also I need to make another method that takes the tree that I have established, and corrects the strings. So the method modifies the parent string, if found, and looks at its children, if found, and replaces those strings with those found in the method parameters. It's sort of like adding a subtree without screwing the entire tree up. Thanks in advance!

bool changeNode(BSTNode *n,char* parentQ, char* leftQ, char* rightQ)
{
  if(n->Q == leftQ)
  {
    n->Q = parentQ;
    n->left = new BSTNode(leftQ);
    n->right = new BSTNode(rightQ);
    return true;
  }
  else if(n->Q == rightQ)
  {
    n->Q = parentQ;
    n->left = new BSTNode(leftQ);
    n->right = new BSTNode(rightQ);
    return true;
  }
  else if(n->Q != leftQ)
  {
    changeNode(n->left,parentQ,leftQ, rightQ);
  }
  else if(n->Q != rightQ)
  {
    changeNode(n->right,parentQ,leftQ,rightQ);
  }
    return false;
}

Answer 1

You didn't even mention what the error was, example input / expected output, but shouldn't you be checking whether the current node actually has a left and right child, before calling the function with those children?

else if(n->Q != parentQ) // <--- you have a typo in this line, "parent"
  {                      //      (and you don't even need the 'if')
    insertNode(n->left,parentQ,leftQ,rightQ);
    insertNode(n->right,parentQ,leftQ,rightQ);
    // in this case you return nothing! corrupted return value
  }

^ this seems very error-prone, especially null-pointer. You should turn it into something like:

    else
      {
        if(n->left != NULL) // take a look at nullptr if you have C++11
          if(insertNode(n->left,parentQ,leftQ,rightQ)) return true;
        if(n->right != NULL)
          if(insertNode(n->right,parentQ,leftQ,rightQ)) return true;
        return false;
      }

Otherwise your true return never gets propagated back beyond the first return, so then you're always returning false unless in the only case where the root of the tree is actually the node you were searching for.

Also, do not compare two char arrays using ==, unless n->Q is actually an std::string. You should use if(strcmp(n->Q, parentQ) == 0) otherwise.

Your second piece of code, however, is just a mess. You need to take a better look at what exactly will be happening on your else if's and see if it is actually doing what you want (hint: it isn't), as you currently only execute at most 1 of the code blocks, even if more than one condition is true.