CODEWITHSUNDEEP
c++vectortree
CallmeACE
CallmeACE

Reputation: 21

Stack overflow when I try to build an octree structure

I want to build an n-dimensional tree. I use a vector to store the children of each node. The code I wrote gives "stack overflow error", and I don't know why, I do use new. I would be very grateful if someone could tell me where I went wrong. 

class Node
{
public:
  int q_number;
  int layer;
  int value;
  vector<Node*> n_list;

  Node(int n):q_number(n),n_list(n) //initialize node vector
  {
  }
};

Node* buildtree(int n,int depth)
{
  Node * node = new Node(depth);

  if(n==depth-1)
  {
    for(int i = 0; i<depth;i++)
    {
      node->n_list[i] = NULL;
      node->n_list[i]->value = i;
      node->n_list[i]->layer = depth-1;
    }
  }
  else
  { 
    for (int i =0;i<depth;i++)
    {               
      node->n_list[i] = buildtree(n++,depth);// span the tree recursively           
      node->n_list[i]->value = i;
      node->n_list[i]->layer = n;   // the layer value
    }
  }

  return node;
}
int main()
{
  Node * tree = buildtree(0,8); // build an octree
}

Upvotes: 1

Views: 377

Answers (1)

Alex Shesterov
Alex Shesterov

Reputation: 27525

As Dolda2000 noticed, you are post-incrementing n when calling buildtree recursively. Thus, n is incremented after its old value (unchanged) has been passed to the function. Thus, you have an infinite stack of buildtree(0,8); calls, which naturally results in stack overflow.

Pre-incrementing — buildtree(++n,depth); — would solve the problem with stack overflow, but that's not what you want in this case, since you make use of n after the recursive call. As I understand your intention, you do not expect the value of n to change after the recursive call.

The solution in your case is just: 

buildtree(n+1,depth);

There's another problem in your code: 

    node->n_list[i] = NULL; // ok, the pointer is NULL now
    node->n_list[i]->value = i; // trying to dereference a NULL pointer => error
    node->n_list[i]->layer = depth-1;

You need either a new Node(...) here, or change vector's value type from Node* to Node, ... or make sure the pointer is properly set before dereferencing it.

P.S. And make sure that n <= depth-1 — by an assertion, or include a comment in code at least to avoid lots of debugging later.

Upvotes: 2

Related Questions