How to write iterative DFS which counts descendants of a node in a tree

Question

I have problem with turning this code:

void dfs(int i = 1) {
  static int preorder = 0;
  d[i].first = ++preorder;
  d[i].second = 1;
  for (list<int>::iterator it = tree[i].begin(); it != tree[i].end(); ++it) {
    dfs(*it);
    d[i].second += d[*it].second;
  }
}

into iterative one. As you can see, it finds preorder number of each node and how many descendants it has. I have to do it, because of memory limitation (data size is up to 10^6).

Thanks in advance.

Answer 1

Finally I've figure it out. It may be not so fast but it is fast enough to get passed through tests without eating too much memory. I needed pointers from child to his father (just 8 MB array called ojciec) and detect if node is first time visited (going down) or not (going up). Here is my code:

void dfs()
{
  int preorder = 0;
  int i;
  stack<int, list<int> > stos;

  stos.push(1);
  while(!stos.empty()) {
    i = stos.top();

    if (order[i] == 0) { // node is first time visited
      order[i] = ++preorder; // set default values
      size[i]  = 1;
    }

    if (dynastia[i] != NULL) // can go left...
      stos.push( pop( &dynastia[i] ) ); // so take first child, remove it and release memory
    else {
      stos.pop();
      size[ojciec[i]] += size[i]; // adding total number of descendants to father
    }
  }
}