Balance

using System;
using System.IO;

namespace ConsoleAppCS
{
    class Program
    {
        static void Main(string[] args)
        {
            BinTree tree = new BinTree();
            using (StreamReader sr = new StreamReader("input.txt"))
            {
                string[] toks = sr.ReadLine().Split();
                foreach (string s in toks)
                    tree.Add(int.Parse(s));
            }
            Console.WriteLine("tree.IsBalanced(): {0}", tree.IsBalanced());
            Tuple<object, object> res =  tree.CanBeBalanced();
            if (res == null)
                Console.WriteLine("Can't balance the tree...");
            else if (res.Item1 == null)
                Console.WriteLine("Tree is already balanced!");
            else
            {
                Console.WriteLine("Tree can be balanced with element from {0} to {1}", res.Item1, res.Item2);
                Console.WriteLine("Adding {0}", res.Item1);
                tree.Add(res.Item1);
                Console.WriteLine("tree.IsBalanced(): {0}", tree.IsBalanced());
            }
        }
    }
}




using System;

namespace ConsoleAppCS
{
    internal class BinTree
    {
        class Node
        {
            public object value;
            public Node leftChild, rightChild;
            public int Counter { get; private set; }
            public Node(object value)
            {
                this.value = value;
                leftChild = rightChild = null;
                Counter = 1;
            }

            public static void Add(ref Node r, object value)
            {
                if (r == null)
                    r = new Node(value);
                else
                {
                    ++r.Counter;
                    if (((IComparable)value).CompareTo(r.value) < 0)
                        Add(ref r.leftChild, value);
                    else
                        Add(ref r.rightChild, value);
                }
            }

            public static void PrintInorder(Node r)
            {
                if (r != null)
                {
                    PrintInorder(r.leftChild);
                    Console.Write(r.value + " ");
                    PrintInorder(r.rightChild);
                }
            }

            public static void PrintPreorder(Node r)
            {
                if (r != null)
                {
                    Console.Write(r.value + " ");
                    PrintPreorder(r.leftChild);
                    PrintPreorder(r.rightChild);
                }
            }

            public static void PrintPostorder(Node r)
            {
                if (r != null)
                {
                    PrintPostorder(r.leftChild);
                    PrintPostorder(r.rightChild);
                    Console.Write(r.value + " ");
                }
            }

            public static Node Search(Node r, object value)
            {
                if (r == null)
                    return null;
                int cmpRes = ((IComparable)r.value).CompareTo(value);
                if (cmpRes == 0)
                    return r;
                else if (cmpRes > 0)
                    return Search(r.leftChild, value);
                else return Search(r.rightChild, value);
            }

            public static bool Delete(ref Node r, object key)
            {
                if (r == null)
                    return false;
                int cmpRes = ((IComparable)r.value).CompareTo(key);
                if (cmpRes > 0)
                    if (Delete(ref r.leftChild, key))
                    {
                        --r.Counter;
                        return true;
                    }
                    else return false;
                else if (cmpRes < 0)
                    if (Delete(ref r.rightChild, key))
                    {
                        --r.Counter;
                        return true;
                    }
                    else return false;
                else if (r.leftChild == null)
                    r = r.rightChild;
                else if (r.rightChild == null)
                    r = r.leftChild;
                else Del(r, ref r.leftChild);

                return true;
            }

            private static void Del(Node r, ref Node l)
            {
                if (l.rightChild != null)
                    Del(r, ref l.rightChild);
                else
                {
                    r.value = l.value;
                    l = l.leftChild;
                }
            }

            public static bool CanBeBalanced(ref Node r, ref object min, ref object max, ref bool needsTo)
            {
                if (r == null)
                    return true;

                int lc = r.leftChild != null ? r.leftChild.Counter : 0;
                int rc = r.rightChild != null ? r.rightChild.Counter : 0;
                int diff = lc - rc;

                if (Math.Abs(diff) > 2)
                    return false;

                if (Math.Abs(diff) == 2)
                    needsTo = true;

                if (diff > 0)
                {
                    min = r.value;
                    return CanBeBalanced(ref r.rightChild, ref min, ref max, ref needsTo) && IsBalanced(r.leftChild);
                }
                else if (diff < 0)
                {
                    max = (int)r.value - 1;
                    return CanBeBalanced(ref r.leftChild, ref min, ref max, ref needsTo) && IsBalanced(r.rightChild);
                }
                else
                {
                    object tempMin = r.value, tempMax = max;
                    bool tmpNeeds = needsTo;
                    if (CanBeBalanced(ref r.rightChild, ref tempMin, ref tempMax, ref tmpNeeds) && IsBalanced(r.leftChild))
                    {
                        min = tempMin;
                        max = tempMax;
                        needsTo = tmpNeeds;
                        return true;
                    }
                    max = (int)r.value - 1;
                    return CanBeBalanced(ref r.leftChild, ref min, ref max, ref needsTo) && IsBalanced(r.rightChild);
                }
            }

            public static bool IsBalanced(Node r)
            {
                if (r == null)
                    return true;

                int lc = r.leftChild == null ? 0 : r.leftChild.Counter;
                int rc = r.rightChild == null ? 0 : r.rightChild.Counter;
                int diff = Math.Abs(lc - rc);

                return diff <= 1 && IsBalanced(r.leftChild) && IsBalanced(r.rightChild);
            }
        }

        Node root;
        object minElem, maxElem;

        public BinTree()
        {
            root = null;
        }

        private BinTree(Node root)
        {
            this.root = root;
        }

        public void Add(object value)
        {
            if (minElem == null || ((IComparable)value).CompareTo(minElem) < 0)
                minElem = value;
            if (maxElem == null || ((IComparable)value).CompareTo(maxElem) > 0)
                maxElem = value;
            Node.Add(ref root, value);
        }

        public void PrintInorder()
        {
            Node.PrintInorder(root);
            Console.WriteLine();
        }

        public void PrintPreorder()
        {
            Node.PrintPreorder(root);
            Console.WriteLine();
        }

        public void PrintPostorder()
        {
            Node.PrintPostorder(root);
            Console.WriteLine();
        }

        public BinTree Search(object value)
        {
            return new BinTree(Node.Search(root, value));
        }

        public void Delete(object key)
        {
            Node.Delete(ref root, key);
            if (key == minElem)
            {
                Node el = root;
                while (el.leftChild != null)
                    el = el.leftChild;
                minElem = el.leftChild.value;
            }
            if (key == maxElem)
            {
                Node el = root;
                while (el.rightChild != null)
                    el = el.rightChild;
                maxElem = el.rightChild.value;
            }
        }

        public bool IsBalanced()
        {
            return Node.IsBalanced(root);
        }

        public Tuple<object, object> CanBeBalanced()
        {
            object min = (int)minElem - 1, max = (int)maxElem + 1;
            bool needs = false;
            bool res = Node.CanBeBalanced(ref root, ref min, ref max, ref needs);

            if (res)
            {
                if (needs)
                    return new Tuple<object, object>(min, max);
                else
                    return new Tuple<object, object>(null, null);
            }
            return null;
        }
    }
}