//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);
}