using System;

namespace _03BinTree
{
    class BinTree
    {
        private class BItem
        {
            public int zahl;
            public BItem kleiner = null, groesser = null;
            public override string ToString()
            {
                string linksText = (kleiner == null) ? "null" : kleiner.zahl.ToString();
                string rechtsText = (groesser == null) ? "null" : groesser.zahl.ToString();

                return $"  {linksText}-{zahl}-{rechtsText}  ";
            }
        }
        BItem root = null;

        public void InsertItem(int Zahl)
        {
            BItem neu = new BItem() { zahl = Zahl };
            if (root == null)
                root = neu;
            else
            {
                bool gefunden = false;
                BItem item = root;
                do
                {
                    if (Zahl < item.zahl)        // links oder rechts?
                    {   // Linker Teilbaum
                        if (item.kleiner == null)  // ist "links" frei?
                        {
                            item.kleiner = neu;
                            gefunden = true;
                        }                       // nein --> links weitersuchen
                        else
                            item = item.kleiner;
                    }
                    else
                    {
                        if (item.groesser == null)  // ist "rechts" frei?
                        {
                            item.groesser = neu;
                            gefunden = true;
                        }                       // nein --> rechts weitersuchen
                        else
                            item = item.groesser;
                    }
                } while (!gefunden);
            }
        }
        public bool FindItem(int zahl)
        {
            BItem item = root;
            while (item != null)
            {
                if (zahl == item.zahl)
                    return true;
                item = (zahl < item.zahl) ? item.kleiner : item.groesser;
            }
            return false;
        }
        private void Print(BItem item)
        {
            if (item != null)
            {
                if (item.kleiner!= null)
                    Print(item.kleiner);
                Console.Write(item.zahl + " ");
                if (item.groesser!=null)
                    Print(item.groesser);
            }
        }
        public void Print()
        {
            Print(root);
            Console.WriteLine();
        }
    }
    class Program
    {
        static void Main(string[] args)
        {
            BinTree bt = new BinTree();
            bt.InsertItem(50);
            bt.InsertItem(25);
            bt.InsertItem(75);
            bt.InsertItem(60);
            bt.InsertItem(80);
            bt.InsertItem(77);
            bt.InsertItem(70);
            bt.InsertItem(50);

            bt.Print();
            Console.WriteLine($"Find(77): {bt.FindItem(77)}");
            Console.WriteLine($"Find(78): {bt.FindItem(78)}");
        }
    }
}