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

Russell Islam Russell Islam · Accepted Answer · 2020-12-01T17:48:25

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++

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

1 Answers