fork download
//print paths in a tree without recursion
#include
#include
#include
using namespace std;
struct node                         
{
       int data;
       vectorchildren;
};
int visited[100];
stack  st;
int count=0;
int n;      
void printpath(node * root)                               //dfs starts here
{
     st.push(root);
     while(visited[0]==0)
     {
         node* v=st.top();
         if(visited[v->data]!=0)                 // leaf nodes or nodes whose all children 
            st.pop();                            // are visited are only popped from the stack
         if(visited[v->data])
            continue;
         cout<data<<" ";
         int flag=0;
         for(int i=0;ichildren.size();i++)      /*check if any of the children have not been visited*/
         {
                 if(visited[v->children[i]->data]==0)
                 {
                      flag=flag||1;
                      st.push(v->children[i]);
                 }
                 else
                       flag=flag||0;
         }
         
         /*if this is the leaf node then mark it visited and
         along with other intermediate nodes whose all the   
         children have been visited.this is continued till we
         reach root which has the value 0 in its data*/
         
         if(flag==0)
         {                                      
                 visited[v->data]=1;                       
                  while(v->data!=0)                         
                  {
                     v=st.top();
                     int flag=0;
                     for(int i=0;ichildren.size();i++)
                     {
                        if(visited[v->children[i]->data]==0)
                          flag=flag||1;
                       else
                         flag=flag||0;
                     }
                        if(flag==0 && v->children.size()!=0)
                          visited[v->data]=1;
                        if(v->data!=0)
                          st.pop();
                  }
                  cout<data=0;
   node* d = new node();
   d->data=1;
   node* m = new node();
   m->data=2;
   node* n = new node();
   n->data=3;
   root->children.push_back(d);
   root->children.push_back(m);
   root->children.push_back(n);
   node* x = new node();
   x->data=4;
   node* y = new node();
   y->data=5;
   node* z = new node();
   z->data=6;
   d->children.push_back(x);
   d->children.push_back(y);
   d->children.push_back(z);
   node* o = new node();
   o->data=7;
   node* p = new node();
   p->data=8;
   n->children.push_back(o);
   n->children.push_back(p);
   printpath(root);
}
   
         
Success #stdin #stdout 0.01s 2860KB
stdin
Standard input is empty
stdout
0 3 8 
0 3 7 
0 2 
0 1 6 
0 1 5 
0 1 4