title: Tree Postorder Traversal performance
body: <p>I tried to work on my own to get iterative postorder traversal. My solution got Time Limited Exceeded in <a href="https://oj.leetcode.com/problems/binary-tree-postorder-traversal/" rel="nofollow">Leetcode Online Judge</a></p>
  
  <pre><code>public List&lt;Integer&gt; postorderTraversalIterativel(TreeNode root) {
      List&lt;Integer&gt; ret = new LinkedList&lt;Integer&gt;();
      Stack&lt;TreeNode&gt; stack = new Stack&lt;TreeNode&gt;();
      TreeNode cur = root;
      while (cur != null || !stack.isEmpty()) {
          if (cur != null) {
              stack.push(cur);
              cur = cur.left;
          } else {
              TreeNode parent = stack.peek(), child = null;
              if (parent.right == null) {
                  // pop hard
                  stack.pop();
                  while (parent.right == child &amp;&amp; !stack.isEmpty()) {
                      child = parent;
                      ret.add(child.val);
                      parent = stack.pop();
                  }
              } else {
                  cur = parent.right;
              }
          }
      }
      return ret;
  }
  </code></pre>
  
  <p>while the official implementation from <a href="http://en.wikipedia.org/wiki/Tree_traversal" rel="nofollow">wikipedia</a> could pass the test.</p>
  
  <pre><code>public List&lt;Integer&gt; postorderTraversalIterativel(TreeNode root) {
      List&lt;Integer&gt; ret = new LinkedList&lt;Integer&gt;();
      Stack&lt;TreeNode&gt; stack = new Stack&lt;TreeNode&gt;();
      TreeNode cur = root, lastVisited = null;
      while (cur != null || !stack.isEmpty()) {
          if (cur != null) {
              stack.push(cur);
              cur = cur.left;
          } else {
              TreeNode parent = stack.peek();
              if (parent.right != null &amp;&amp; lastVisited != parent.right) {
                  // make sure pop all the node has right child of the
                  // previous pop
                  cur = parent.right;
              } else {
                  stack.pop();
                  ret.add(parent.val);
                  lastVisited = parent;
              }
          }
      }
      return ret;
  }
  </code></pre>
  
  <p>by inspecting the code, I am unable to see why my implementation is slower than the official one. Could anyone point out what's happening? (It's possible that my solution is logically wrong, but the one failed my solution in timing I have unit tested, and the unit test finishes quick ...). Any comments are welcome.</p>
  
  <pre><code>public void testPostorderTraversal1() {
      TreeNode root = new TreeNode(3);
      TreeNode right = new TreeNode(1);
      TreeNode rightLeft = new TreeNode(2);
      root.right = right;
      right.left = rightLeft;
  
      List&lt;Integer&gt; list = new LinkedList&lt;Integer&gt;();
      list.add(2);
      list.add(1);
      list.add(3);
  
      assertEquals(list.toString(), sut.postorderTraversal(root).toString());
  }
  
  public void testPostorderTraversal2() {
      TreeNode root = new TreeNode(1);
      TreeNode right = new TreeNode(2);
      root.right = right;
  
      List&lt;Integer&gt; list = new LinkedList&lt;Integer&gt;();
      list.add(2);
      list.add(1);
  
      assertEquals(list.toString(), sut.postorderTraversal(root).toString());
  }
  </code></pre>