Binary Tree Post Order Traversal Iterative solution

May 22, 2016

 Warm up the post order traversal after 10 hours intensive study of binary tree lowest common ancestor.

 First version, there is a bug in the code: out of memory on line 59

https://gist.github.com/jianminchen/4092880aef47a501ce2c3097531744fa

Need to reset the runner node as stack.Pop().

 Correct version:

https://gist.github.com/jianminchen/9eaa168499642430baa463fef6471c76

Review solutions:

1. User two stacks:
https://github.com/jianminchen/leetcode-tree/blob/master/TreePostOrderIterative.cs

2. Review previous blog:
http://juliachencoding.blogspot.ca/2015/06/leetcode-post-order-binary-tree.html

3. Previous blog: Leetcode 106: binary tree serialization - Leetcode
http://juliachencoding.blogspot.ca/search/label/post%20order%20traversal

4. Review blog:
http://juliachencoding.blogspot.ca/2016/01/divide-and-conquer-preorder-traversal.html

5. The solution can be optmized - redundant code.
https://github.com/jianminchen/leetcode-tree/blob/master/TreePostOrderIterative_PrevVarirable.cs

Questions and answers:
1. How is the practice?

Julia made a bug in first time writing, she did not notice that she needs to maintain runner when nodes in a row are popped out, so only one node with value 3 (test case: a tree with post order traversal 1 - 9) will be popped out, node with value 4 cannot be popped out.

First, wrong answer.
Second, the code runs on the test case - tree 1-9 will stop on node with value 4, and then, keep adding node with value 4 forever.

line 57:  while(stack.Count > 0 && (stack.Peek().right == null || stack.Peek().right == runner))
                {
                    TreeNode node = (TreeNode)stack.Pop(); // bug - out of memory - should be runner = (TreeNode)stack.Pop()
                    postTraversal.Add(node.val);
                }

line 63:    if(stack.Count == 0)
                    break;
                else
                    runner = stack.Peek().right;

Julia was not sure if runner should be reset. She does not have strong clues at that time.

Lessons: Need to stop, and take 3-5 minutes to do some reasoning and analysis. Do not rush to finish coding even if you have ideas to implement.

Actually, while loop - line 57 is maintained by runner variable, previous's node is using runner variable.

2. Tips about practice?
Do not rush to compile/ running the code, ask yourself, if you can make the code no compiler error, no run time error, with correct answer, without compiling and running the code, you start to use reasoning and analysis to poke every place possible going wrong.

one of practice goals: reasoning and analysis.