using System;
using System.Collections.Generic;
using System.Text;

namespace _2313_trees
{
    class Program
    {
        static void Insert(ref TreeNode cur, string toInsert)
        {
            if (cur == null)
            {
                cur = new TreeNode(toInsert);
            }
            else if (String.Compare(cur.data, toInsert) == 1)
            {
                // cur is bigger that toInsert
                Insert(ref cur.left, toInsert);
            }
            else if (String.Compare(cur.data, toInsert) == -1)
            {
                // cur is smaller that toInsert
                Insert(ref cur.right, toInsert);
            }
        }

        static void PrintTree(TreeNode cur)
        {
            if (cur != null)
            {
                PrintTree(cur.right);
                Console.WriteLine(cur.data);
                PrintTree(cur.left);
            }
        }

        static void DS(ref int a)
        {
            Console.WriteLine("a in DS " + a);
            a = 42;
            Console.WriteLine("a in DS after " + a);
        }

        static void Main(string[] args)
        {
//            int b = 9;
//            Console.WriteLine("before in main " + b);
//            DS(ref b);
//            Console.WriteLine("after in main " + b);

            TreeNode root = null;

            Insert(ref root, "apple");
            Insert(ref root, "pencil");
            Insert(ref root, "x-ray");
            Insert(ref root, "john");
            Insert(ref root, "casaba");
            Insert(ref root, "chihuahua");
            Insert(ref root, "aardvark");

            PrintTree(root);
        }
    }
}