1

I'm getting a segmentation fault on my program when I try to insert to a binary search tree. Here's the declaration of the node:

template < class T > class binTreeNode {
friend class binTree < T >;
friend class binSTree < T >;
public:
    // default constructor
    binTreeNode ( const T& newData =T( ), binTreeNode < T >* newLeft = 0, binTreeNode < T >* newRight = 0 ) {
        data = newData;
        left = newLeft;
        right = newRight;
    }
private:
    T data; // data value in node
    binTreeNode < T > *left, *right; // links to other nodes
};

The functions below are all new, everything else (like height functions and constructors) are all done in the parent class, and shouldn't really be relevant. The new functions are:

template <class T>
class binSTree : public binTree<T> {
public:
    void insert (const T& newData) {
        if (root == NULL) {
            root = new binTreeNode<T>(newData);
        }
        else
            insert(root,newData);
    }
    bool search (const T& x) const {
        if (root != NULL)
            return search(root,x);
        else
            return false;
    }
    bool remove (const T& x) {
        if (root == NULL)
            return false;
        remove(root,x);
        return true;
    }
protected:
    binTreeNode<T>* root;
private:
    void insert (binTreeNode<T>*& ptr, const T& x) {
        if (ptr == NULL) {      // Base case, actual insertion
            binTreeNode<T>* newNode;
            newNode = new binTreeNode<T>(x);
            ptr = newNode;
            return;
        }
        if (x == ptr->data)
            return;
        else if (x < ptr->data)
            insert(ptr->left,x);
        else
            insert(ptr->right,x);
        return;
    }
    bool search (binTreeNode<T>* ptr, const T& x) const {
        if (ptr->data == x)
            return true;
        else if (x < ptr->data && ptr->left != NULL)
            search(ptr->left,x);
        else if (ptr->right != NULL)
            search(ptr->right,x);
        else
            return false;
    }
    binTreeNode<T>* remove (binTreeNode<T>* ptr, const T& x) {
        if (ptr == NULL)
            return NULL;
        else if (ptr->data == x && leaf(ptr)) {
            delete ptr;
            ptr = NULL;
            return ptr;
        }
        else if (ptr->data == x && !leaf(ptr))
            return ptr;
        else if (x < ptr->data) {
            ptr->left = remove(ptr->left,x);
            return ptr;
        }
        else {
            ptr->right = remove(ptr->right,x);
            return ptr;
        }
    }
    bool leaf (binTreeNode<T>* node) const {
        if (node->left != NULL || node->right != NULL)
            return false;
        return true;
    }
};

The segmentation fault, according to valgrind, is in the private insert in the conditional where I check if (x == ptr->data). Does anyone have any idea why this is? I've completely hit a wall. Thanks :3

5
  • Have you confirmed that ptr contains a valid address? Commented Apr 5, 2012 at 23:40
  • To expand upon that, NULL checks only work if the pointer was initialized to NULL (or happens to have a value of the same). If I do int *ptr; ptr is likely not NULL, it's value is indeterminate. Commented Apr 5, 2012 at 23:41
  • My constructor sets the data to NULL if no actual data is set, so it should either be NULL or valid data. Commented Apr 5, 2012 at 23:53
  • Is the type of T in your driver function a built-in type, or one of your own classes? If it's one of your classes, does it define a custom == operator? Commented Apr 6, 2012 at 0:03
  • They're integers, nothing special. Commented Apr 6, 2012 at 0:12

1 Answer 1

4

There is a problem in your remove code that may or may not be the cause of your crash, but should definitely be fixed: when you recursively remove ptr->left or ptr->right that results in deleting the node, you should also set the left or right pointer in the parent to NULL; otherwise you open up your code to errors associated with dangling pointers.

Sign up to request clarification or add additional context in comments.

3 Comments

My driver program doesn't even get to the remove function, so that's not this particular issue, but thanks.
The insert function suffers from the same problem. When you add a node that has no children, initialize its left and right pointers to NULL.
I modified it to set ptr->left and ptr->right to null, it didn't change anything.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.