Tuesday, March 20, 2012

Postorder traversal of a binary tree without recursion


void BSTree::postorder()
{
stack<Node*> st;
set<Node*> visit;
if(root.get() == NULL)
return;
st.push(root.get());

while(!st.empty())
{
Node* curr = st.top();
if(curr->left.get() != NULL && visit.find(curr->left.get()) == visit.end())
st.push(curr->left.get());
else if(curr->right.get() != NULL && visit.find(curr->right.get()) == visit.end())
st.push(curr->right.get());
else
{
cout<<curr->data<<'\t';
visit.insert(curr);
st.pop();
}
}
}

No comments:

Post a Comment