using System;
using System.Collections.Generic;

namespace ConsoleApp1
{
    class Program
    {
        static void Main(string[] args)
        {
            DrzewoBST drzewoBST = new DrzewoBST(0);
            drzewoBST.Push(10);
            drzewoBST.Push(11);
            drzewoBST.Push(12);
            drzewoBST.Push(13);
            drzewoBST.Push(14);
            drzewoBST.Push(15);
            drzewoBST.Push(16);
            drzewoBST.Push(17);
            drzewoBST.Push(18);
            drzewoBST.Push(19);
            Console.WriteLine("SHOWIN");
            drzewoBST.SHOWINBST(drzewoBST.korzenbst);
            Console.WriteLine("SHOWPRE");
            drzewoBST.SHOWPREBST(drzewoBST.korzenbst);
            Console.WriteLine("SHOWPOST");
            drzewoBST.SHOWPOSTBST(drzewoBST.korzenbst);
            Console.ReadKey();
        }
    }
    class Wezel
    {
        public Wezel rodzic;
        public Wezel lewe;
        public Wezel prawe;
        public int wartosc;
        public Wezel(int wartosc)
        {
            this.wartosc = wartosc;
        }
    }
    class DrzewoBST : Wezel
    {
        public Wezel korzenbst;
        public int lengthbst;
        public int glebokoscbst;
        public DrzewoBST(int wartosc) : base(wartosc)
        {
            this.korzenbst = new Wezel(wartosc);
            this.lengthbst = 1;
            this.glebokoscbst = 0;

        }
        public Wezel znajdzRodzica(int numer)
        {
            List<int> droga = new List<int>();
            while (numer > 0)
            {
                --numer;
                numer = numer / 2;
                droga.Add(numer);
            }
            droga.Reverse();
            var rodzic = this.korzenbst;
            for (int i = 1; i < droga.Count; i++)
            {
                if (droga[i] % 2 == 1)
                {
                    rodzic = rodzic.lewe;
                }
                else
                {
                    rodzic = rodzic.prawe;
                }
            }
            return rodzic;
        }
        public void Push(int wartosc)
        {
            var dziecko = new Wezel(wartosc);
            var rodzic = this.znajdzRodzica(this.lengthbst);
            dziecko.rodzic = rodzic;
            if (rodzic.wartosc <= wartosc)
            {
                if (rodzic.lewe == null)
                {
                    rodzic.lewe = new Wezel(wartosc);
                }
                else
                {
                    rodzic.lewe = dziecko;
                }
            }
            else
            {
                if(rodzic.prawe == null)
                {
                    rodzic.prawe = new Wezel(wartosc);
                }
                else
                {
                    rodzic.prawe = dziecko;
                }

            }
            this.lengthbst++;
        }
        public void SHOWINBST(Wezel w)
        {
            if (w == null)
            {
                return;
            }
            SHOWINBST(w.lewe);
            Console.WriteLine(w.wartosc + " ");
            SHOWINBST(w.prawe);
        }
        public void SHOWPREBST(Wezel w)
        {
            if (w == null)
            {
                return;
            }
            Console.WriteLine(w.wartosc + " ");
            SHOWPREBST(w.lewe);
            SHOWPREBST(w.prawe);
        }
        public void SHOWPOSTBST(Wezel w)
        {
            if (w == null)
            {
                return;
            }
            SHOWPOSTBST(w.lewe);
            SHOWPOSTBST(w.prawe);
            Console.WriteLine(w.wartosc + " ");
        }
    }

}