language: C++ 4.7.2 (gcc-4.7.2)
date: 329 days 21 hours ago
link:
visibility: public 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100

//print paths in a tree without recursion
#include<iostream>
#include<vector>
#include<stack>
using namespace std;
struct node                         
{
       int data;
       vector<node*>children;
};
int visited[100];
stack <node*> 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<<v->data<<" ";
         int flag=0;
         for(int i=0;i<v->children.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;i<v->children.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<<endl;
         }
     }
}
main()
{
   n=8;
   for(int i=0;i<9;i++)
       visited[i]=0;
   node*root = new node();                         //tree construction
   root->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);
}