?using System;
using System.Collections.Generic;
using System.Text;

namespace HeightBalancedTree
{
    class Node
    {
        public int data;
        public Node lchild;
        public Node rchild;
        public int BF;
        public Node preNode;
    }
    class BalancedTree
    {
        Node root = new Node();
        int[] array = new int[10];
        static int index = 0;

        public BalancedTree()
        {
            root = null;
        }
        public void insert()
        {
            Node parent = null;
            Node current = null;
            Node newNode = new Node();
            Console.Write("Input the data:");
            newNode.data = Convert.ToInt32(Console.ReadLine());
            newNode.BF = 0;
            if (root == null)
            {
                root = newNode;
                root.preNode = null;
            }
            else
            {
                find(newNode.data, ref parent, ref current);
                if (current != null)
                {
                    Console.WriteLine("Duplicates are not allowed!");
                    return;
                }
                else
                {
                    if (newNode.data < parent.data)
                    {
                        parent.lchild = newNode;
                    }
                    else
                    {
                        parent.rchild = newNode;
                    }
                    newNode.preNode = parent;
                    Node ptr = parent;
                    int i = index - 1;
                    while (ptr != null)
                    {
                        ptr.BF += array[i--];
                        if (ptr.BF == 0)
                        {
                            Console.WriteLine("It is a balanced tree !");
                            return;
                        }
                        else if ((ptr.BF != 0) && (ptr.BF != 1) && (ptr.BF != -1))
                        {
                            Console.WriteLine("Not balanced !");
                            balance(ptr, newNode);
                            return;
                        }
                        ptr = ptr.preNode;
                    }
                    Console.WriteLine("It is a balanced tree!");
                }
            }
        }
        public void balance(Node keyNode, Node newNode)
        {
            Console.WriteLine("Balance the tree...\n");
            Console.WriteLine("Before:");
            traverse();
            Node ptrParent = new Node();
            ptrParent = keyNode.preNode;

            if (keyNode.BF == 2)
            {
                if (keyNode.lchild.BF == 1) //LL
                {
                    Node tempNode = keyNode.lchild;
                    keyNode.lchild = tempNode.rchild;
                    tempNode.rchild = keyNode;
                    tempNode.rchild.preNode = keyNode;
                    keyNode.preNode = tempNode;

                    if (keyNode == root)
                    {
                        tempNode.preNode = null;
                        root = tempNode;
                        root.BF = 0;
                        root.rchild.BF = 0;
                    }
                    else
                    {
                        tempNode.preNode = ptrParent;
                        keyNode = tempNode;
                        keyNode.BF = 0;
                        keyNode.rchild.BF = 0;
                    }
                }
                else
                {
                    if (keyNode.lchild.rchild.BF == 0) //LR
                    {
                        newNode.lchild = keyNode.lchild;
                        newNode.rchild = keyNode;
                        keyNode.lchild.preNode = newNode;
                        keyNode.preNode = newNode;
                        if (root == keyNode)
                        {
                            newNode.preNode = null;
                            root = newNode;
                            root.lchild.rchild = null;
                            root.rchild.lchild = null;
                            root.lchild.BF = 0;
                            root.rchild.BF = 0;
                        }
                        else
                        {
                            newNode.preNode = ptrParent;
                            keyNode = newNode;
                            keyNode.lchild.rchild = null;
                            keyNode.rchild.lchild = null;
                            keyNode.lchild.BF = 0;
                            keyNode.rchild.BF = 0;
                        }
                    }
                    else if (keyNode.lchild.rchild.BF == 1) //LR(L)
                    {
                        Node tempNode = newNode.preNode;
                        ptrParent.lchild = tempNode;
                        tempNode.rchild = keyNode;
                        keyNode.preNode = tempNode;
                        keyNode.lchild.rchild = tempNode.lchild;
                        tempNode.lchild.preNode = keyNode.lchild;
                        tempNode.lchild = keyNode.lchild;
                        keyNode.lchild.preNode = tempNode;

                        if (keyNode == root)
                        {
                            tempNode.preNode = null;
                            root = tempNode;
                            keyNode.BF = 0;
                            root.lchild.BF = 0;
                            root.rchild.BF = -1;
                        }
                        else
                        {
                            tempNode.preNode = ptrParent;
                            tempNode.BF = 0;
                            tempNode.lchild.BF = 0;
                            tempNode.rchild.BF = -1;
                        }
                        tempNode.rchild.lchild = null;
                    }
                    else //LR(R)
                    {
                        Node tempNode = newNode.preNode;
                        tempNode.lchild = keyNode.lchild;
                        keyNode.lchild = tempNode.rchild;
                        tempNode.rchild = keyNode;
                        keyNode.lchild.preNode = tempNode;
                        tempNode.rchild.preNode = keyNode;
                        keyNode.preNode = tempNode;
                        if (keyNode == root)
                        {
                            tempNode.preNode = null;
                            root = tempNode;
                            root.BF = 0;
                            root.lchild.BF = 1;
                            root.rchild.BF = 0;
                        }
                        else
                        {
                            tempNode.preNode = ptrParent;
                            keyNode = tempNode;
                            keyNode.BF = 0;
                            keyNode.lchild.BF = 1;
                            keyNode.rchild.BF = 0;
                        }
                        keyNode.lchild.rchild = null;
                    }
                }
            }
            else if (keyNode.BF == -2)
            {
                if (keyNode.rchild.BF == -1) //RR
                {
                    Node tempNode = keyNode.rchild;
                    keyNode.rchild = tempNode.lchild;
                    tempNode.lchild.preNode = keyNode;
                    tempNode.lchild = keyNode;
                    keyNode.preNode = tempNode;
                    if (keyNode == root)
                    {
                        tempNode.preNode = null;
                        root = tempNode;
                        root.BF = 0;
                        root.lchild.BF = 0;
                    }
                    else
                    {
                        tempNode.preNode = ptrParent;
                        tempNode.BF = 0;
                        tempNode.lchild.BF = 0;
                    }
                }
                else
                {
                    if (keyNode.rchild.lchild.BF == 0) //RL
                    {
                        newNode.lchild = keyNode;
                        newNode.rchild = keyNode.rchild;
                        //keyNode.preNode.rchild = newNode;

                        keyNode.preNode = newNode;
                        keyNode.rchild.preNode = newNode;
                        if (keyNode == root)
                        {
                            newNode.preNode = null;
                            root = newNode;
                            root.lchild.rchild = null;
                            root.rchild.lchild = null;
                            root.lchild.BF = 0;
                            root.rchild.BF = 0;
                        }
                        else
                        {
                            ptrParent.rchild = newNode;
                            newNode.preNode = ptrParent;
                            //keyNode = newNode;
                            newNode.lchild.rchild = null;
                            newNode.rchild.lchild = null;
                            newNode.lchild.BF = 0;
                            newNode.rchild.BF = 0;
                        }
                    }
                    else if (keyNode.rchild.lchild.BF == 1) //RL(L)
                    {
                        Node tempNode = newNode.preNode;
                        tempNode.rchild = keyNode.rchild;
                        keyNode.rchild = tempNode.lchild;
                        tempNode.lchild = keyNode;