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

namespace Exercise_1
{
    public class Node<T> : IComparable<Node<T>> where T : IComparable<T>
    {
        public T Value { get { return Value; } set { Value = value; } }
        public Node<T> Left { get; set; }
        public Node<T> Right { get; set; }
        public Node<T> Parent { get; set; }
        void Insert(T value) {
            Node<T> node = this;
            Node<T> previous = null;
            bool left = false;
            while (node != null) {
                if (node.Value.Equals(value))
                    return;
                else {
                    //search left if value is smaller
                    bool searchLeft = Convert.ToBoolean(value.CompareTo(node.Value));

                    if (searchLeft) {
                        previous = node;
                        left = true;
                        node = node.Left; //search left
                    }
                    else {
                        previous = node;
                        left = false;
                        node = node.Right; //search right
                    }
                }

            }//while
            if (left)
                previous.Left = new Node<T>(value, previous);
            else
                previous.Right = new Node<T>(value, previous);
        } //insert

        public Node<T> Find(T value, Node<T> test = null) { //returns null if not found
            Node<T> node = this;
            while (node != null) {
                if (node.Value.Equals(value))
                    return node;
                else {
                    //search left if value is smaller
                    bool searchLeft = Convert.ToBoolean(value.CompareTo(node.Value));

                    if (searchLeft)
                        node = node.Left; //search left
                    else
                        node = node.Right; //search right
                }

            } //while
            return null;
        } //find


        // Constructor
        public Node(T value, Node<T> parent=null) { //if no second parameter, this will be the root of a new tree
            //throw new Exception();
            Value = value;
            Parent = parent;
            Left = null;
            Right = null;
        }

        //private static int CompareElements(IComparable x, IComparable y) {
        //    return x.CompareTo(y);
        //}

        public int CompareTo(Node<T> rhs) {
            return Value.CompareTo(rhs.Value);
        }

        public bool Equals(Node<T> rhs) {
            return this.Value.Equals(rhs.Value);
        }


        public override string ToString() {
            /*
             * Simply do print left, print self, print right
             */
            if (this.Left != null)
                this.Left.ToString();

            Console.WriteLine(this.Value);

            if (this.Right != null)
                this.Right.ToString();

            return "";
        }

        public static Node<T> MakeTree(params T[] list) {
            Node<T> root = null;
            if (list.Length > 0) {
                root = new Node<T>(list[0]);
                for (int i = 1; i < list.Length; i++) {
                    root.Insert(list[i]);
                }
            }
            return root;
        }
    }
    class Program
    {
        static void Main(string[] args) {
            //Node<int> test;
            //test = new Node<int>(5);
            Node<char>.MakeTree('p', 'x', 's', 't', 'r', 'q', 'b', 'a');
            System.Console.Read();
        }
    }
}