BST insert in c++

Question

I'm learning c++ and writing a binary search tree. The following is the code I wrote for my insert method.

BSTNode * BST::Insert(const std::string & v) {
 BSTNode *n = !root ? root = new BSTNode(v) : Insert_Helper(v,root);
 if(n) size++;
 return n;
}

BSTNode * BST::Insert_Helper(const std::string & v, BSTNode *n) {
 if(!n->value.compare(v))
  return NULL; // already have v
 else if(n->value.compare(v) > 0) // v goes to the left
  if(n->left) return Insert_Helper(v,n->left);
  else return n->left = new BSTNode(v);
 else // v goes to the right
  if(n->right) Insert_Helper(v,n->right);
  else return n->right = new BSTNode(v);
}

The bug I'm getting goes like this: It all works fine and dandy till I try to insert a duplicate node, it doesn't add a new node yet it increments count.

By observing in GDB, I've found that when I try to add a string that I already have, Insert_Helper works correctly and returns NULL, this value however (on my machine) is something like 0x6, which is out of bounds, of course, but not 0x0 like I thought it would be. I think this causes an issue at the point where I have the if(n) statement. In this case n evaluates to true, and so increments size one more than it should.

Furthermore, at this point in my program, the nodes continue to get added correctly, but my insert function continues to return 0x6 as the address, even though they really are in valid locations in memory that I can access.

Can anyone give me any pointers as to what I might be doing wrong? It's probably something dumb and obvious, but then again most bugs are.

Answer 1

Your compiler probably should have spotted this, but this line near the end of your helper:

if(n->right) Insert_Helper(v,n->right);

You probably should return whatever Insert_Helper returns:

if(n->right) return Insert_Helper(v,n->right);

Answer 2

You can change if(n) size++ to if (n != NULL) size++