title: NonRecursive PostOrder Binary Tree Traversal using parallel stacks
body: <p>I'm suppose to take this pseucode-ish algorithm of a nonrecursive postorder binary tree traversal and actually implement it into code. Essentially i'm suppose to create two parallel stacks, one to save the references to the nodes, and one to save the integer value 1 or 2, to tell whether the left or right subtree have been visited. I created the algorithm based off what they gave me but for some reason its only printing some of the numbers and not in the correct order, i feel like i interpreted it like it should be but its just now working, any help would be nice.</p>
  
  <p>Heres what they want me to do:</p>
  
  <pre><code>1.create stack(s)
  2. current = root;
  3.v = 0;
  4. if (current is null)
      the binary tree is empty
  5. if (current is not null)
      a. push current onto stack;
      b. push 1 onto stack;
      c. current = current.lLink;
  6. while (stack is not empty)
        if (current is not null and v is 0)
        {
            push current and 1 onto stack;
            current = current.lLink
        }
        else
        {
            pop stack into current and v;
            if ( v == 1)
            {
                push current and 2 onto stack;
                current = current.rLink;
                v = 0;
            }
            else
                visit current;
        }
  </code></pre>
  
  <p>And here is my implementation of it:</p>
  
  <pre><code>public void nonRecursivePostTraversal()
  {
      LinkedStackClass&lt;BinaryTreeNode&lt;T&gt; &gt; stack
      = new LinkedStackClass&lt;BinaryTreeNode&lt;T&gt; &gt;();//create stack
  
      //create parallel stack of integers
      LinkedStackClass&lt;Integer&gt; stackInt = new LinkedStackClass&lt;Integer&gt;();
  
      BinaryTreeNode&lt;T&gt; current;
      current = root;
  
      Integer v = 0;
  
      if (current == null)
          stack = null;
  
      if   (current != null)
      {
          stack.push(current);
          v = 1;
          stackInt.push(v);
          current = current.lLink;
      }
  
  
      while (!stack.isEmptyStack())
          if (current != null &amp;&amp; v == 0)
          {
              stack.push(current);
              v = 1;
              stackInt.push(v);
              current = current.lLink;
  
          }
          else
          {
              current = (BinaryTreeNode&lt;T&gt;) stack.peek();
              stack.pop();
              v = (Integer) stackInt.peek();
              stackInt.pop();
              if (v == 1)
              {
                  stack.push(current);
                  v = 2;
                  stackInt.push(v);
                  current = current.rLink;
                  v = 0;
              }
              else
                  System.out.print(current.info + " ");
          }
  
  }//end alg
  </code></pre>