using System;

using System.Collections.Generic;

public class Program

{

    public static void Main()

    {

        Console.WriteLine("Hello World");

    }

    public static List<int> InorderTraversal(TreeNode root) {

        List<int> visited = new List<int>();

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

        TreeNode cur = root;

        // if current node is not null "OR" stack is not empty

        while (cur != null || stack.Count > 0) {

            // if current node is not null

            while (cur != null)

            {

                // push current node to stack

                stack.Push(cur);

                // keep add left nodes. eventually current node will not have left child

                cur = cur.left;

            }

            // if current node is null, pop its parent node from stack. parent node becomes current node.

            cur = stack.Pop();

            // add the current node to visited

            visited.Add(cur.val);

            // right child becomes current node

            cur = cur.right;

        }

        return visited;

    }

}

​

 public class TreeNode {

      public int val;

      public TreeNode left;

      public TreeNode right;

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

  }