techInterview Discussion 

A part of techInterview.org: answers to technical interview questions.
Your host: Michael Pryor 
Ken, to do the postorder without marking you need to compare child pointers of the top node on the stack with your current node. If the current node is its left children then you need to access its right child next. Otherwise it's about the time to access the top node and then pop it from the stack. A visited mark only makes the algorithm clear. It's not necessary.
For postorder traversal non recursively : use stacks
start with inserting root into the stack, then pop root and insert its left and right node. continue popping printing elements from stack and then adding popped nodes left n right nodes into stack. It will print nodes in post order traversal.
Ray: You're correct that a visited mark is not needed. However, the algorithm is slightly more complex than how you describe it. See my code below.
Misty: What you describe is not postorder at all. Rather, it's preorder (but mirrored). I.e., instead of going (node, left, right), you're going (node, right, left). Here's my attempt at succinct solutions for preorder, inorder and postorder traversal (all nonrecursive): void preorder(const Node* node) { std::stack<const Node*> stack; while (node != NULL  !stack.empty()) { if (node == NULL) { node = stack.top(); stack.pop(); } process(node>value); if (node>right != NULL) stack.push(node>right); node = node>left; } } void inorder(const Node* node) { std::stack<const Node*> stack; while (node != NULL  !stack.empty()) { if (node == NULL) { node = stack.top(); stack.pop(); process(node>value); node = node>right; } if (node != NULL) { stack.push(node); node = node>left; } } } void postorder(const Node* node) { std::stack<const Node*> stack; while (node != NULL  !stack.empty()) { if (node == NULL) { while (!stack.empty() && node == stack.top()>right) { node = stack.top(); stack.pop(); process(node>value); } node = stack.empty() ? NULL : stack.top()>right; } if (node != NULL) { stack.push(node); node = node>left; } } } 
Powered by FogBugz