Binary Tree Inorder Traversal - Iterative solution - with test case, and some comment.

BinaryTreeInorderTraversal.cs

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace InorderTraversal
{
    public class TreeNode
    {
        public TreeNode left;
        public TreeNode right;
        public int val;

        public TreeNode(int v)
        {
            val = v; 
        }
    }

    class Program
    {
        static void Main(string[] args)
        {
            TreeNode n1 = new TreeNode(4);
            n1.left = new TreeNode(2);
            n1.left.left = new TreeNode(1);
            n1.left.right = new TreeNode(3);

            List<TreeNode> inorderNodes = inorderIterative(n1);
            TreeNode[] arr = inorderNodes.ToArray();

            TreeNode t2 = new TreeNode(3);
            t2.left = new TreeNode(2);
            t2.left.left = new TreeNode(1);
            t2.right = new TreeNode(5);
            t2.right.left = new TreeNode(4);
            t2.right.right = new TreeNode(6);
            t2.right.right.right = new TreeNode(7);

            List<TreeNode> inorderNodes2 = inorderIterative(t2);
            TreeNode[] arr2 = inorderNodes2.ToArray();
        }

        /*
         * Warmup iterative solution:   May 25, 2016
         * Prepare a while loop, 
         *    inside the loop, 
         *    First task is to push node and its left child to the stack, until the first node 
         *    in inorder traversal.
         *    Check if the stack is empty or not, if it is empty, exit the while loop. 
         *    
         * Julia, your task is to prove that the code is simple as possible, cover all test cases:
         * 1. First, argue that line 88, why to check "if stack is empty, break the while loop" 
         * before outputting any node in the stack. 
         *    otherwise, if the stack is emtpy, then, line 91: execution run time error
         * 2. Second, argue that output of inorder traversal nodes is not in inner loop. 
         *    If there are more than 1 in a row to output, then the outer while loop (line 79) 
         *    will take care of it. 
         * 3. Third, argue that line 94: runner = runner.right; 
         *    it does not matter that right child exists or not, line 81 will take care of null. 
         *    Complete one iteration - 
         *    Push nodes into stack, then first node in inorder is on the top of stack, 
         *    If stack is empty, break; otherwise, ready to pop top one from the stack, 
         *    and then, move runner to its right child. 
         *    
         */
        public static List<TreeNode> inorderIterative(TreeNode root)
        {
            List<TreeNode> inorderNodes = new List<TreeNode>(); 

            if (root == null)
                return null;

            Stack<TreeNode> stack = new Stack<TreeNode>();

            TreeNode runner = root;

            while (true)
            {
                while (runner != null)   // line 81
                {
                    stack.Push(runner);
                    runner = runner.left; 
                }


                if (stack.Count == 0)    // line 88 
                    break;

                runner = stack.Pop();
                inorderNodes.Add(runner);

                runner = runner.right; // line 94
            }

            return inorderNodes; 
        }
    }
}