using System;
using System.Collections;
using System.Collections.Generic;
using System.ComponentModel;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using NUnit.Framework.Constraints;

namespace BinaryTrees
{
    public class BinaryTree<TKey> : IEnumerable<TKey> where TKey : IComparable
    {
        private class Node<TKey>
        {
            public TKey Value;
            public Node<TKey> Left, Right;
            public int Weight { get; set; }
            public Node(TKey value)
            {
                this.Value = value;
                this.Right = null;
                this.Left = null;
                Weight = 0;
            }

        }

        public int Count { get; private set; }
        private int treeHeight;
        private Node<TKey> root;

        public BinaryTree()
        {
            treeHeight = -1;
            root = null;
            Count = 0;

        }

        public void Add(TKey value)
        {
            this.Count++;
            if (root == null)
            {
                root = new Node<TKey>(value);
                return;
            }
            var tempHeight = -1;
            var tempRoot = this.root;
            while (tempRoot != null)
            {
                tempRoot.Weight++;
                if (tempRoot.Value.CompareTo(value) < 0)
                {
                    if (tempRoot.Right == null)
                    {
                        tempRoot.Right = new Node<TKey>(value);
                        return;
                    }
                    tempRoot = tempRoot.Right;
                }
                else
                {
                    if (tempRoot.Left == null)
                    {
                        tempRoot.Left = new Node<TKey>(value);
                        return;
                    }
                    tempRoot = tempRoot.Left;
                }
            }
        }

        public bool Contains(TKey value)
        {
            var tempRoot = this.root;
            while (tempRoot != null)
            {
                if (tempRoot.Value.Equals(value))
                    return true;
                if (tempRoot.Value.CompareTo(value) < 0)
                    tempRoot = tempRoot.Right;
                else
                    tempRoot = tempRoot.Left;
            }
            return false;
        }

        public IEnumerator<TKey> GetEnumerator()
        {
            return GetEnumerator();
        }

        IEnumerator IEnumerable.GetEnumerator()
        {
            var currentRoot = this.root;
            var queue = new Stack<Node<TKey>>();
            var left = Count;

            while(left != 0)
            {
                if(currentRoot.Left == null)
                {
                    yield return currentRoot.Value;
                    left--;
                }
                else
                {
                    queue.Push(currentRoot);
                    currentRoot = currentRoot.Left;
                }
            }
        }
    }
}