Signup/Sign In
Ask Question
Not satisfied by the Answer? Still looking for a better solution?

How to Perform a postorder traversal of an N-ary tree without recursion

How do I perform a postorder traversal of an N-ary tree without recursion?
by

1 Answer

akshay1995
Ok, so in n-ary tree the structure of node will look like this-)

struct Node{
int val;
vector<Node> childs;
Node(int x,vector<int> child){
val=x;
childs=child;
}
};

//Here we will only look towards the traversing part, for building n-ary tree ,you can take help from gfg or leetcode .

vector<int> postorder(struct Node* root){
if(root==NULL)
return {};
vector<int> pos;// for storing traversal
stack<Node*> st;
st.push(root);
while(!st.empty())
{
Node
curr=st.top();
st.pop();
pos.push_back(curr->val);
// node values are entered in reverse order so we have to reverse //it again in end
for(auto x: curr->childs)// looping through the childs of curr node
{
if(!x)
st.push(x);
}
}
reverse(pos.begin(),pos.end());
return pos;
}

Login / Signup to Answer the Question.