using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.IO;
using System.Runtime.Serialization;
using System.Runtime.Serialization.Formatters.Binary;
using System.Xml.Serialization;
using System.Runtime.Serialization.Formatters.Soap;

namespace ConsoleApplication20
{
    [Serializable]
    public class BinarySearchTree<T>
    {
        [Serializable]
        public class BinarySearchTreeNode<T>
        {
            T _data;
            BinarySearchTreeNode<T> _left;
            BinarySearchTreeNode<T> _right;

            public BinarySearchTreeNode()
            {
                _data = default(T);
                _left = null;
                _right = null;
            }

            public BinarySearchTreeNode(T data)
            {
                _data = data;
                _left = null;
                _right = null;
            }

            public T Data
            {
                get
                {
                    return _data;
                }

                set
                {
                    _data = value;
                }
            }

            public BinarySearchTreeNode<T> Left
            {
                get
                {
                    return _left;
                }

                set
                {
                    _left = value;
                }
            }

            public BinarySearchTreeNode<T> Right
            {
                get
                {
                    return _right;
                }

                set
                {
                    _right = value;
                }
            }

        }

        //public delegate int Compare(T a, T b);
        //Compare _cmp;

        BinarySearchTreeNode<T> _root;

        Comparison<T> _cmp;

        public BinarySearchTreeNode<T> Root
        {
            get
            {
                return _root;
            }
        }

        public BinarySearchTree(Comparison<T> cmp)
        {
            _root = null;
            _cmp = cmp;
        }

        public BinarySearchTree()
        {
            _root = null;
            _cmp = Comparer<T>.Default.Compare;
        }

        public void TraverseInOrder(BinarySearchTreeNode<T> start)
        {
            if (start != null)
            {
                Console.WriteLine(start.Data.ToString());
                TraverseInOrder(start.Left);
                TraverseInOrder(start.Right);
            }
        }

        public BinarySearchTreeNode<T> Find(T data)
        {
            if (_root == null)
            {
                return null;
            }

            BinarySearchTreeNode<T> current = _root;

            while (current != null)
            {
                if (_cmp(data, current.Data) == 0)
                {
                    return current;
                }

                if (_cmp(data, current.Data) < 0)
                {
                    current = current.Left;
                }
                else if (_cmp(data, current.Data) > 0)
                {
                    current = current.Right;
                }
            }

            return null;
        }

        public bool Remove(T data, BinarySearchTreeNode<T> start = null, BinarySearchTreeNode<T> prev = null)
        {
            if (_root == null)
            {
                return false;
            }

            BinarySearchTreeNode<T> curr = start;

            if (start == null)
            {
                curr = _root;
            }

            if (_cmp(data, curr.Data) < 0)
            {
                return Remove(data, curr.Left, curr);
            }
            else if (_cmp(data, curr.Data) > 0)
            {
                return Remove(data, curr.Right, curr);
            }

            if (_cmp(data, curr.Data) == 0)
            {
                if (curr.Left == null && curr.Right == null)
                {
                    if (prev == null)
                    {
                        _root = null;
                        return true;
                    }
                    else if (_cmp(curr.Data, prev.Data) < 0)
                    {
                        prev.Left = null;
                    }
                    else if (_cmp(curr.Data, prev.Data) > 0)
                    {
                        prev.Right = null;
                    }
                }
                else if (curr.Left != null && curr.Right == null)
                {
                    if (prev == null)
                    {
                        _root = _root.Left;
                    }
                    else if (_cmp(curr.Data, prev.Data) < 0)
                    {
                        prev.Left = curr.Left;
                    }
                    else if (_cmp(curr.Data, prev.Data) > 0)
                    {
                        prev.Right = curr.Left;
                    }
                }
                else if (curr.Left == null && curr.Right != null)
                {
                    if (prev == null)
                    {
                        _root = _root.Right;
                    }
                    else if (_cmp(curr.Data, prev.Data) < 0)
                    {
                        prev.Left = curr.Right;
                    }
                    else if (_cmp(curr.Data, prev.Data) > 0)
                    {
                        prev.Right = curr.Right;
                    }
                }
                else
                {

                    BinarySearchTreeNode<T> successor = curr.Right;
                    BinarySearchTreeNode<T> successorPrev = curr.Right;

                    while (successor.Left != null)
                    {
                        successorPrev = successor;
                        successor = successor.Left;
                    }

                    if (successor != successorPrev)
                    {
                        successorPrev.Left = successor.Right;
                        successor.Right = curr.Right;
                    }
                    else
                    {
                        curr.Right = successor.Right;
                    }

                    successor.Left = curr.Left;

                    if (prev == null)
                    {
                        _root = successor;
                    }
                    else
                    {
                        if (_cmp(curr.Data, prev.Data) < 0)
                        {
                            prev.Left = successor;
                        }
                        else if (_cmp(curr.Data, prev.Data) > 0)
                        {
                            prev.Right = successor;
                        }
                    }
                }

                return true;
            }

            return false;
        }

        public void Add(T data)
        {
            BinarySearchTreeNode<T> node = new BinarySearchTreeNode<T>(data);

            if (_root == null)
            {
                _root = node;
                return;
            }

            BinarySearchTreeNode<T> curr = _root;
            BinarySearchTreeNode<T> prev = null;

            while (curr != null)
            {
                prev = curr;
                if (_cmp(node.Data, curr.Data) < 0)
                {
                    curr = curr.Left;
                }
                else
                {
                    curr = curr.Right;
                }
            }

            if (_cmp(node.Data, prev.Data) < 0)
            {
                prev.Left = node;
            }
            else
            {
                prev.Right = node;
            }
        }

    }

    class Program
    {
        public static void SerializeToXml(string filename, object obj)
        {
            XmlSerializer serializer = new XmlSerializer(obj.GetType());

            using (Stream fs = new FileStream(filename, FileMode.Create))
            {
                serializer.Serialize(fs, obj);
            }
        }

        public static object DeserializeFromXml(string filename, Type type)
        {
            XmlSerializer serializer = new XmlSerializer(type);

            object result = null;

            using (Stream fs = new FileStream(filename, FileMode.Open, FileAccess.Read))
            {
                result = serializer.Deserialize(fs);
            }

            return result;
        }

        public static object DeserializeFromBinary(string filename)
        {
            object obj = null;

            using (Stream s = new FileStream(filename, FileMode.Open, FileAccess.Read))
            {
                BinaryFormatter bf = new BinaryFormatter();
                obj = bf.Deserialize(s);
            }

            return obj;
        }

        public static void SerializeToBinary(string filename, object obj)
        {
            using (Stream s = new FileStream(filename, FileMode.Create))
            {
                BinaryFormatter bf = new BinaryFormatter();
                bf.Serialize(s, obj);
            }
        }

        public static void TestBinarySearchTreeClass()
        {
            Comparison<int> cmp = Comparer<int>.Default.Compare;
            BinarySearchTree<int> btree = new BinarySearchTree<int>(cmp);

            Console.WriteLine("Testing BinarySearchTree class Add method...");
            btree.Add(8);
            btree.Add(10);
            btree.Add(14);
            btree.Add(13);
            btree.Add(3);
            btree.Add(1);
            btree.Add(6);
            btree.Add(7);
            btree.Add(4);
            btree.Add(15);
            btree.Add(16);

            Console.WriteLine("The constructed binary search tree:");
            btree.TraverseInOrder(btree.Root);

            Console.WriteLine("Testing BinarySearchTree class Remove method (removing a leaf node)...");
            btree.Remove(16);

            Console.WriteLine("The tree after removing node \"16\": ");
            btree.TraverseInOrder(btree.Root);

            Console.WriteLine("Testing BinarySearchTree class Remove method (removing a node with the only child)...");
            btree.Remove(14);

            Console.WriteLine("The tree after removing node \"14\": ");
            btree.TraverseInOrder(btree.Root);

            Console.WriteLine("Testing BinarySearchTree class Remove method (removing a node with two children)...");
            btree.Remove(3);

            Console.WriteLine("The tree after removing node \"3\": ");
            btree.TraverseInOrder(btree.Root);

            Console.WriteLine("Testing BinarySearchTree class Remove method (removing the root)...");
            btree.Remove(8);

            Console.WriteLine("The tree after removing node \"8\": ");
            btree.TraverseInOrder(btree.Root);

            string filename = @"C:\Users\DEFAULTUSER\Desktop\SavedBST111.xml";

            Console.WriteLine("Testing BinarySearchTree class binary serialization...");

            SerializeToXml(filename, btree);

            Console.WriteLine("Testing BinarySearchTree class binary deserializtion...");
            BinarySearchTree<int> btree2 = null;

            btree2 = (BinarySearchTree<int>)DeserializeFromXml(filename, typeof(BinarySearchTree<int>));

            Console.WriteLine("Deserialized tree: ");
            btree2.TraverseInOrder(btree2.Root);
        }

        static void Main(string[] args)
        {
            TestBinarySearchTreeClass();

            Console.ReadKey();
        }
    }
}