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

namespace ConsoleApp1
{
    public class Csomopont
    {
        public int Adat { get; set; }
        public Csomopont Bal { get; set; }
        public Csomopont Jobb { get; set; }
        public Csomopont(int adat) {
            Adat = adat;
            Bal = null;
            Jobb = null;
        }
    }

    public class BinFa
    {
        public Csomopont Gyoker { get; private set; }

        public void Beszuras(int adat)
        {
            Gyoker = BeszurasRekurziv(Gyoker, adat);
        }

        private Csomopont BeszurasRekurziv(Csomopont csomopont, int adat)
        {
            if (csomopont == null)
            {
                return new Csomopont(adat);  
            }

            if (adat < csomopont.Adat)
            {
                csomopont.Bal = BeszurasRekurziv(csomopont.Bal, adat);
            }
            else if (adat > csomopont.Adat)
            {
                csomopont.Jobb = BeszurasRekurziv(csomopont.Jobb, adat);
            }
            return csomopont;
        }

        public bool Kereses(int adat)
        {
            return KeresesRekurziv(Gyoker, adat);
        }

        private bool KeresesRekurziv(Csomopont csomopont, int adat)
        {
            if (csomopont == null)
            {
                return false;
            }

            if (adat == csomopont.Adat)
            {
                return true;
            }

            return 
                adat < csomopont.Adat 
                ? KeresesRekurziv(csomopont.Bal, adat)
                : KeresesRekurziv(csomopont.Jobb, adat);
        }

        public void Torles(int adat)
        {
            Gyoker = TorlesRekurziv(Gyoker, adat);
        }

        private Csomopont TorlesRekurziv(Csomopont csomopont, int adat) {
            if (csomopont == null)
            {
                return null;
            }

            if (adat < csomopont.Adat)
            {
                csomopont.Bal = TorlesRekurziv(csomopont.Bal, adat);
            } else if (adat > csomopont.Adat)
            {
                csomopont.Jobb = TorlesRekurziv(csomopont.Jobb, adat);
            } else
            {
                if (csomopont.Bal == null && csomopont.Jobb == null)
                {
                    return null ;
                }

                if (csomopont.Bal == null)
                {
                    return csomopont.Jobb;
                }

                if (csomopont.Jobb == null)
                {
                    return csomopont.Bal;
                }

                csomopont.Adat = MinimumErtek(csomopont.Jobb);
                csomopont.Jobb = TorlesRekurziv(csomopont.Jobb, csomopont.Adat);
            }
            return csomopont;
        }

        private int MinimumErtek(Csomopont csomopont)
        {
            while (csomopont.Bal != null)
            {
                csomopont = csomopont.Bal;
            }

            return csomopont.Adat;
        }

        public void InorderBejaras()
        {
            Console.WriteLine("Inorder bejárás:");
            InorderRekurziv(Gyoker);
            Console.WriteLine();
        }

        private void InorderRekurziv(Csomopont csomopont)
        {
            if (csomopont == null)
            {
                return;
            }

            InorderRekurziv(csomopont.Bal);
            Console.WriteLine(csomopont.Adat + " ");
            InorderRekurziv(csomopont.Jobb);
        }

        public void PreorderBejaras()
        {
            Console.WriteLine("Preorder bejárás: ");
            PreorderRekurziv(Gyoker);
            Console.WriteLine();
        }

        private void PreorderRekurziv(Csomopont csomopont)
        {
            if (csomopont == null)
            {
                return;
            }
            Console.WriteLine(csomopont.Adat + " ");
            PreorderRekurziv(csomopont.Bal);
            PreorderRekurziv(csomopont.Jobb);
        }

        public void PostorderBejaras()
        {
            Console.WriteLine("Postorder bejárás: ");
            PostorderRekurziv(Gyoker);
            Console.WriteLine();
        }

        private void PostorderRekurziv(Csomopont csomopont)
        {
            if (csomopont == null)
            {
                return;
            }
            PostorderRekurziv(csomopont.Bal);
            PostorderRekurziv(csomopont.Jobb);
            Console.WriteLine(csomopont.Adat + " ");
        }
    }
    internal class Program
    {
        static void Main(string[] args)
        {
            BinFa fa = new BinFa();

            fa.Beszuras(50);
            fa.Beszuras(30);
            fa.Beszuras(70);
            fa.Beszuras(20);
            fa.Beszuras(40);
            fa.Beszuras(60);
            fa.Beszuras(80);

            fa.InorderBejaras();
            fa.PreorderBejaras();
            fa.PostorderBejaras();

            Console.WriteLine($"\nKeresés 40 {fa.Kereses(40)}");
            Console.WriteLine($"\nKeresés 100 {fa.Kereses(100)}");

            Console.WriteLine("\nTörlés 50 (gyökér):");
            fa.Torles(50);
            fa.InorderBejaras();

            Console.ReadLine();
        }
    }
}
