using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace AllBalancedTrees
{
    class Program
    {
        static void Main(string[] args)
        {
            char[] nodes = { 'A', 'B', 'C', 'D', 'E' };

            AllBalancedTrees<char> AllBalancedTrees = new AllBalancedTrees<char>(); 

            foreach (char[] a in AllBalancedTrees.allBalancedTreeCombinations(nodes))
            {
                foreach (char c in a)
                {
                    Console.Write(c + " ");
                }
                Console.WriteLine();
            }

            Console.ReadKey();
        }
    }

    class AllBalancedTrees<T>
    {
        public IEnumerable<T[]> allBalancedTreeCombinations(T[] nodes)
        {
            T[] result;
            if (nodes.Length == 1)
            {
                yield return nodes;
            }
            else if (nodes.Length == 2)
            {
                yield return nodes;
                T[] nodes2 = new T[2];
                nodes2[0] = nodes[1];
                nodes2[1] = nodes[0];
                yield return nodes2;
            }
            else if (nodes.Length % 2 == 1)
            {
                int mid = (nodes.Length - 1) / 2;
                T[] left = new T[mid];
                T[] right = new T[mid];
                Array.Copy(nodes, 0, left, 0, mid);
                Array.Copy(nodes, mid + 1, right, 0, mid);
                foreach (T[] l in allBalancedTreeCombinations(left))
                {
                    foreach (T[] r in allBalancedTreeCombinations(right))
                    {
                        result = new T[nodes.Length];
                        result[0] = nodes[mid];
                        foreach (T[] a in allMergeCombinations(l, r))
                        {
                            Array.Copy(a, 0, result, 1, a.Length);
                            yield return result;
                        }
                    }
                }
            }
            else
            {
                int mid = (nodes.Length) / 2;
                T[] left = new T[mid];
                T[] right = new T[mid - 1];
                Array.Copy(nodes, 0, left, 0, mid);
                Array.Copy(nodes, mid + 1, right, 0, mid - 1);
                foreach (T[] l in allBalancedTreeCombinations(left))
                {
                    foreach (T[] r in allBalancedTreeCombinations(right))
                    {
                        result = new T[nodes.Length];
                        result[0] = nodes[mid];
                        foreach (T[] a in allMergeCombinations(l, r))
                        {
                            Array.Copy(a, 0, result, 1, a.Length);
                            yield return result;
                        }
                    }
                }

                mid = nodes.Length / 2 - 1;
                left = new T[mid];
                right = new T[mid + 1];
                Array.Copy(nodes, 0, left, 0, mid);
                Array.Copy(nodes, mid + 1, right, 0, mid+1);
                foreach (T[] l in allBalancedTreeCombinations(left))
                {
                    foreach (T[] r in allBalancedTreeCombinations(right))
                    {
                        result = new T[nodes.Length];
                        result[0] = nodes[mid];
                        foreach (T[] a in allMergeCombinations(l, r))
                        {
                            Array.Copy(a, 0, result, 1, a.Length);
                            yield return result;
                        }
                    }
                }


            }
        }

        public IEnumerable<T[]> allMergeCombinations(T[] firstArray, T[] secondArray)
        {
            if (firstArray.Length == 0)
            {
                yield return secondArray;
            }
            else if (secondArray.Length == 0)
            {
                yield return firstArray;
            }
            else
            {
                T[] result;

                T[] firstMinusOne;
                firstMinusOne = new T[firstArray.Length - 1];
                Array.Copy(firstArray, 1, firstMinusOne, 0, firstMinusOne.Length);
                foreach (T[] a in allMergeCombinations(firstMinusOne, secondArray))
                {
                    result = new T[firstArray.Length + secondArray.Length];
                    result[0] = firstArray[0];
                    Array.Copy(a, 0, result, 1, a.Length);
                    yield return result;
                }

                T[] secondMinusOne;
                secondMinusOne = new T[secondArray.Length - 1];
                Array.Copy(secondArray, 1, secondMinusOne, 0, secondMinusOne.Length);
                foreach (T[] a in allMergeCombinations(firstArray, secondMinusOne))
                {
                    result = new T[firstArray.Length + secondArray.Length];
                    result[0] = secondArray[0];
                    Array.Copy(a, 0, result, 1, a.Length);
                    yield return result;
                }

            }
        }
    }
}