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

namespace BinaryTrees
{
    public class BinaryTree<T> : IEnumerable<T>
        where T : IComparable

    {
        private Node root;

        public int Count
        {
            get;
            private set;
        }

        public class Node
        {
            public Node Left;
            public Node Right;
            public T Value;
        }

        public BinaryTree()
        {
            root = new Node();
        }

        public void Add(T value)
        {
            var current = root;

            while (true)
            {
                if (Count == 0)
                {
                    current.Value = value;
                    Count++;
                    break;
                }

                if (value.CompareTo(current.Value) <= 0)
                {
                    if (current.Left == null)
                    {
                        current.Left = new Node { Value = value };
                        Count++;
                        break;
                    }
                    else
                        current = current.Left;
                }

                else
                {
                    if (current.Right == null)
                    {
                        current.Right = new Node { Value = value };
                        Count++;
                        break;
                    }
                    else
                        current = current.Right;
                }
            }
        }

        public bool Contains(T key)
        {
            var current = root;
            while (true)
            {
                if (Count == 0)
                    return false;

                if (current == null)
                    return false;

                var compare = key.CompareTo(current.Value);

                if (compare == 0)
                    return true;

                current = compare < 0
                    ? current.Left
                    : current.Right;
            }
        }

        public IEnumerator<T> GetEnumerator()
        {
            var stack = new Stack<Node>();

            var current = root;

            while (true)
            {
                if (current != null)
                {
                    stack.Push(current);
                    current = current.Left;
                }

                else if (stack.Count != 0)
                {
                    current = stack.Pop();
                    yield return current.Value;
                    current = current.Right;
                }

                else
                    break;
            }
        }

        IEnumerator IEnumerable.GetEnumerator()
        {
            return GetEnumerator();
        }
    }
}