C++ Adding 2nd Element to BST - Segmentation Fault

Question

So I built a BST based off of the example in class. My peers' trees all work fine, however, I am getting a segmentation fault when I add a second element. I have isolated the error coming from this line - 'if(current->left == NULL){' I am not sure why it is resulting in a segmentation fault and how to avoid it. I will leave the related insertNode code as well as the Node class as I feel it might be a problem there.

template <class T>
void BST<T>::insertNode(T value){
  TreeNode<T> *node = new TreeNode<T>(value);


  if(isEmpty()){
    cout << "Is root" << endl;
    root = node;
  }else{
    cout << "Is not root" << endl;
    TreeNode<T> *parent = NULL;
    TreeNode<T> *current = root;
    cout << "Starting Loop" << endl;
    while(true){
      parent = current;

      if(value < current->key){
        cout << "less tahn" << endl;
        //Left
        current = current->left;
        cout <<"left" << endl;
        if(current == NULL){
          //we found our location/insertion point
          cout << "Found Spot" << endl;
          parent->left = node;
          break;
        }
        cout << "Not NULL" << endl;
      }
      else {
        //Right
        cout << "Right" << endl;
        current = current->right;
        if(current == NULL){
          //we found our location/insertion point
          cout << "Found Spot" << endl;
          parent->right = node;
          break;
        }
      }
    }
  }
}

And the treeNode class -

template <class T>
class TreeNode{
  public:
    TreeNode();
    TreeNode(T k);
    ~TreeNode();

    T key;
    TreeNode *left;
    TreeNode *right;
};
template <class T>
TreeNode<T>::TreeNode(){
  left = NULL;
  right = NULL;
}

template <class T>
TreeNode<T>::TreeNode(T k){
  left = NULL;
  right = NULL;
  key = k;
}

before you check if `current->left == NULL` you should check if `current == NULL` — SHR, Dec 01 '20 at 17:15

score 1 · Answer 1 · answered Dec 01 '20 at 17:48

1

This builds upon what SHR said. When you execute the line current = current->left, there is a chance that current->left of the previous current is null.

This means that when you perform the check if (current->left == NULL), it will result in segmentation fault because there is no left.

You can rewrite the conditional to be something like:

if (current && !current->left){
...
}

By doing so, you check to see first if current is not null, and if it is, only then will it look at the left pointer of the node. Or you can just check before hand to see if (current).

It is also fully sufficient and encouraged to check for NULL by performing if (node) instead of doing if (node == NULL). This explains why: Checking for NULL pointer in C/C++

answered Dec 01 '20 at 17:48

Russell Islam

206
1
8

Thank you! This is a lot of very helpful information. I substituted in the code you gave, but I am still having some troubles though. Now, it simply skips over the if statement, as it is not true now. Fair enough, however, if there is no current - it should insert the node to the tree instead of aborting the insert. Should I put the current = current->left AFTER the if statement? It seems to work, but I am not sure if the tree is holding its structure correctly. Thank you! – Christian Groen Dec 01 '20 at 19:00
EDIT - just tested it and it does not seem to insert anything. Is the root not storing correctly if current is set to root? – Christian Groen Dec 01 '20 at 19:07

C++ Adding 2nd Element to BST - Segmentation Fault

1 Answers1