simple binary search tree. Segmentation Fault

Question

Just a simple BST to print numbers inorder. Couldn't figure out what I did wrong.

#include <iostream>
using namespace std;

class bst {
 private:
  bst* root;
  bst* left;
  bst* right;
  int value;

 public:
  bst(const int& numb) : root(NULL), left(NULL), right(NULL) {
    value = numb;
  }

  void insert(const int& numb) {
    if (numb < value) {
      if (left == NULL) {
        left = new bst(numb);
        left->root = left;
      } else { 
        left->insert(numb);
      }
    } else if (numb > value) {
      if (right == NULL) {
        right = new bst(numb);
        right->root = right;
      } else {
       left->insert(numb);  
      }
    } else if (numb == value) {
      cout << "duplicated value" << endl;
    }
  }

  void inorder() {
    if (left == NULL) cout << value << endl;
    else left->inorder();
    right->inorder();
  }
};


int main() {
  bst tree(5);
  tree.insert(7);
  tree.insert(1);
  tree.insert(3);
  tree.insert(2);
  tree.insert(9);
  tree.insert(10);
  return 0;
}

If this is your full code, you didn't follow the Rule of 3 (or 5). — chris, Jun 01 '12 at 03:54
Basically you need a destructor (which you should always have if your class has a pointer), but also a copy constructor, and assignment operator (and move stuff in C++11), or those pointers wreak havoc. http://stackoverflow.com/questions/4172722/what-is-the-rule-of-three — chris, Jun 01 '12 at 04:04

score 3 · Answer 1 · answered Jun 01 '12 at 03:57

3

Line 29 should read:

 right->insert(numb);

where it currently reads:

 left->insert(numb);

I highly recommend looking into gdb for solving situations like this.

answered Jun 01 '12 at 03:57

Mark Roberts

462
4
6

It also seems like some refactoring into a method could have prevented this kind of bug. – Mark Roberts Jun 01 '12 at 04:00
mark, could you explain how you use gdb to find this error? I could only track down to insert function. – ihm Jun 01 '12 at 04:00
I looked through the stack trace and noticed that the problem didn't happen on the first iteration through the code. Then printed some values along the way and noticed that value wasn't what I'd really expected it to be. Then looking at the data led me to the algorithmic error. – Mark Roberts Jun 01 '12 at 04:03
could you explain it step by step? I am very new to gdb – ihm Jun 01 '12 at 04:05
@ihm: Use `help` command and poke around. The basic commands are `run`, `exit`, `break `, `step`. – nhahtdh Jun 01 '12 at 04:13

score 1 · Answer 2 · answered Jun 01 '12 at 03:54

1

inorder() should be:

if (left != NULL) left->inorder();
cout << value << endl;
if (right != NULL) right->inorder();

I assume the rest are correct.

answered Jun 01 '12 at 03:54

nhahtdh

55,989
15
126
162

thanks for replying. as you can see, I didn't call inorder() in main. it already gave me Segmentation fault. – ihm Jun 01 '12 at 03:55
@ihm: Well, consider this a fix to your `inorder()` code, then. – nhahtdh Jun 01 '12 at 04:01

score 1 · Answer 3 · answered Jun 01 '12 at 04:00

1

Logic errors throughout.

Crash is here:

  if (right == NULL) { 
    right = new bst(numb); 
    right->root = right; 
  } else { 
   left->insert(numb);   
  }

The else case shold use right, not left.

answered Jun 01 '12 at 04:00

Michael

66
1

score 1 · Answer 4 · answered Jun 01 '12 at 04:45

At least as I see it, your fundamental design is flawed. Although I realize many text books (and such) describe a tree as a recursive structure where each node has two sub-trees, I've never found that a very good way to design the code.

At least in my experience, in actual code, you're (much) better off separating the notion of a node in the tree from the notion of an entire tree. Only the tree should be visible to the outside world; node should be hidden away inside the tree, invisible to the outside world.

class bst {
    class node {
        int value;
        node *left;
        node *right;

        // ...

    };

    // ...

    node *root;   
};

I'd then split insert into two pieces: a public function that takes a value, and just forwards to the second function with the root as the starting point. The second actually traverses the three and inserts the new item:

// public interface:
void insert(int v) {    
    insert(new node(v), root);
}

// private workhorse:
void insert(node *n, node *&pos) {
    if (pos == NULL)
        pos = n;
    else if (n->value < pos->value)
        insert(n,pos->left);
    else if (n->value > pos->value)
        insert(n,pos->right);
            else
                // duplicate value.
}

Likewise, inorder gets split into a public and private pair, with the public providing only an interface, and the private one doing all the real work:

// public interface:
void inorder() {
    inorder(root);
}

// private worker
void inorder(node *n) {
    if (n==NULL)
        return;
    inorder(n->left);
    std::cout << n->value << endl;
    inorder(n->right);
}

For what it's worth: yes, I have tested this code and it does work at least with the input you used in you main. It does have shortcomings though. For example, both insert and inorder traverse the tree recursively, so a large, badly imbalanced tree could lead to stack overflow. It's fairly easy to do insertion iteratively, but for real use you usually just switch to some sort of balanced tree instead.

simple binary search tree. Segmentation Fault

4 Answers4