using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
 
namespace BST
{
    class BST
    {
         
        class Wezel
        {
            public int dane;
            public Wezel lewe;
            public Wezel prawe;
            public Wezel(int wartosc)
            {
                this.dane = wartosc;
                lewe = null;
                prawe = null;
            }
        }
        class BinarySearchTree
        {
            public Wezel korzen;
            static int zlicz;
            public BinarySearchTree()
            {
                korzen = null;
            }
             
 
            public Wezel dodajWezel(int dane)
            {
                Wezel tmp = new Wezel(dane);
                if (korzen == null)
                    korzen = tmp;
                zlicz++;
                return tmp;
            }
             
 
            public void Wstaw(Wezel korzen, Wezel nowyWezel)
            {
                while (korzen != null)
                {
                    if (nowyWezel.dane > korzen.dane)
                    {
                        if (korzen.prawe == null)
                        {
                            korzen.prawe = nowyWezel;
                            break;
                        }
                        korzen = korzen.prawe;
                    }
                    else
                    {
                        if (korzen.lewe == null)
                        {
                            korzen.lewe = nowyWezel;
                            break;
                        }
                        korzen = korzen.lewe;
                    }
                }
            }
             
 
            public void inorder(Wezel korzen)
            {
                if (korzen != null)
                {
                    inorder(korzen.lewe);
                    Console.Write(korzen.dane + " ");
                    inorder(korzen.prawe);
                }
            }
            public void preorder(Wezel korzen)
            {
                if (korzen != null)
                {
                    Console.Write(korzen.dane + " ");
                    preorder(korzen.lewe);
                    preorder(korzen.prawe);
                }
            }
            public void postorder(Wezel korzen)
            {
                if (korzen != null)
                {
                    postorder(korzen.lewe);
                    postorder(korzen.prawe);
                    Console.Write(korzen.dane + " ");
                }
            }
        }
        static void Main(string[] args)
        {
            BinarySearchTree bst = new BinarySearchTree();
             
            bst.Wstaw(bst.korzen, bst.dodajWezel(21));
            bst.Wstaw(bst.korzen, bst.dodajWezel(19));
            bst.Wstaw(bst.korzen, bst.dodajWezel(7));
            bst.Wstaw(bst.korzen, bst.dodajWezel(19));
            bst.Wstaw(bst.korzen, bst.dodajWezel(16));
            bst.Wstaw(bst.korzen, bst.dodajWezel(13));
            bst.Wstaw(bst.korzen, bst.dodajWezel(8));
            bst.Wstaw(bst.korzen, bst.dodajWezel(22));
 
            Console.WriteLine("Inorder: ");
            bst.inorder(bst.korzen);
            Console.WriteLine();
            Console.WriteLine("Preorder: ");
            bst.preorder(bst.korzen);
            Console.WriteLine();
            Console.WriteLine("Postorder: ");
            bst.postorder(bst.korzen);
            Console.ReadKey();
        }
    }
}