using System;
namespace BinaryTrees
{
    public class TreeNode<T>
    {
        public TreeNode<T> Left { get; set; }
        public TreeNode<T> Right { get; set; }
        public T Key { get; private set; }

        public TreeNode(T key)
        {
            Key = key;
        }
    }

    public class BinaryTree<T>
	where T : IComparable
    {
        public TreeNode<T> Root;
        public void Add(TreeNode<T> root, T key)
        {
            while (true)
            {
                if (root.Key.CompareTo(key) <= 0)
                {
                    if (root.Right == null)
                    {
                        root.Right = new TreeNode<T>(key);
                        break;
                    }
                    root = root.Right;
                }
                else
                {
                    if (root.Left == null)
                    {
                        root.Left = new TreeNode<T>(key);
                        break;
                    }
                    root = root.Left;
                }
            }
        }

        public void Add(T key)
        {
            if (Root == null)
            {
                Root = new TreeNode<T>(key);
            }
            else
            {
                Add(Root, key);
            }
        }

        public bool Contains(T key)
        {
            TreeNode<T> previusRoot = null;
            var currentRoot = Root;
            while (currentRoot != null)
            {
                if (currentRoot.Key.CompareTo(key) == 0)
                {
                    break;
                }
                if (currentRoot.Key.CompareTo(key) <= 0)
                {
                    previusRoot = currentRoot;
                    currentRoot = currentRoot.Right;
                }
                else
                {
                    previusRoot = currentRoot;
                    currentRoot = currentRoot.Left;
                }
            }
            return currentRoot != null;
        }
    }
}