Ex 10.4-3 of introduction to algorithms

Question:
Write an O(n)-time nonrecursive procedure that, given an n-node binary tree, prints out the key of each node in the tree. Use a stack as an auxiliary data structure.

Answer:
This isn't a difficult question. But the skill of turning a recursive algorithm to non-recursive algorithm is so important, it worths a blog post.

The data structure for tree node used in this post is defined as:
  class TreeNode
  {
  public:
      int value;
      TreeNode* left; // left child node
      TreeNode* right; // right child node
  }

The simplest and cleanest algorithm for binary tree traversal is the recursion. As shown below:
  void inOrderTraversalRecursive(TreeNode* node)
  {
      if(Null == node)
          return;
      inOrderTraversalRecursive(node->left); // visit left sub-tree first
      visit(node); // visit current node
      inOrderTraversalRecursive(node->right); // visit right sub-tree
  }

In this algorithm, each time we goes down a level to the calling stack, a new stack frame will be created for the new function call. Then the context changes to the new stack frame. And the node is kept on the previous stack frame. In current stack frame, node is the left or right child of last stack frame's node. With the help of stack, after a function call is finished, the context changes back to the previous stack frame and consequently gets back to the parent node. Because this stack is managed automatically be the compiler, this algorithm becomes so simple. But this stack isn't unlimited, if the tree's height is large enough, the stack may exhaust. In order to get over this limit, we can use a heap (whose limit is far larger.) based stack data structure and manage it ourselves.

This is done in a loop. Each iteration of the loop is regarded as a function call in recursive version. At proper point of the iteration, we must push/pop node from/to stack so that the context of the iteration can be maintained.
In recursive version, if node is not null, we need to save current node in stack (push) and change node to node->left. Otherwise, the function call returns right away, which means the node is restored (pop) to the value in last call stack frame. After the left sub-tree has been visited, we visit current node.
Then we save (push) current node again and change node to node->right to visit right sub-tree. After it's done, we need to restore (pop) node. But as we can see in the recursive version, the node isn't used at all after the right sub-tree has been visited. That's to say, it's not necessary to save context before we visit right sub-tree any more. This procedure can be omitted in this case.
The last thing to determine is the termination condition. In what situation can we terminate the loop? First, it's clear that the stack should be empty when the loop terminates. But this isn't enough, the node should be null as well to terminate the loop.

  void inOrderTraversalStack(TreeNode* root)
  {
      typedef std::stack<TreeNode*> TreeStack;
      TreeStack stack;
      TreeNode *node = root;
      while(NULL != node || !stack.empty())
      {
          if(NULL != node)
          {
              stack.push(node);
              node = node->left;
          }
          else
          {
              node = stack.top();
              stack.pop();
              visit(node);
              node = node->right;
          }
      }
  }