THREE

//////// עץ בינארי ///////////
        // החזרת סכום ערכים ברמה בעץ
        static int printFloorSum(BinTreeNode<int> t, int floor,int sum = 0)
        {
            if (t != null)
            {
                if (floor == 0)
                {
                    sum = sum + t.GetInfo();
                    return sum;
                }

                return (printFloorSum(t.GetLeft(), floor - 1, sum) + printFloorSum(t.GetRight(), floor - 1, sum));

            }
            return 0;


        }
        // מיון עץ

        // מציאת ערך מקסימלי
        static int getTreeMax(BinTreeNode<int> t, int max = 0)
        {
            if (t != null)
            {
                if (t.GetInfo() > max)
                {
                    max = t.GetInfo();
                }
                return (Math.Max((getTreeMax(t.GetLeft(),max)),getTreeMax(t.GetRight(),max)));
            }
            return max;
        }
        // מציאת ערך מינימאלי
        static int getTreeMin(BinTreeNode<int> t, int min)
        {
            if (t != null)
            {
                if (t.GetInfo() < min)
                {
                    min = t.GetInfo();
                }
                return (Math.Min((getTreeMin(t.GetLeft(), min)), getTreeMin(t.GetRight(), min)));

            }
            return min;

        }
        // מחיקת צומת בידיעה שכל בניה הבאים יימחקו גם כן
        static void deleteValueTree(BinTreeNode<int> t, BinTreeNode<int> s)
        {
            if (t != null)
            {
                if (t.GetLeft() == s)
                {
                    t.SetLeft(null);
                }
                else if (t.GetRight() == s)
                {
                    t.SetRight(null);
                }
                deleteValueTree(t.GetLeft(),s);
                deleteValueTree(t.GetRight(),s);

            }


        }
        // איפוס ערך בעץ
        static void zeroForValueTree(BinTreeNode<int> t, BinTreeNode<int> s)
        {
            if (t != null)
            {
                if (t == s)
                {
                    t.SetInfo(0);
                }
                zeroForValueTree(t.GetLeft(), s);
                zeroForValueTree(t.GetRight(), s);
            }

        }
        // מיון עץ בינארי
        static Queue<int> sortTree(BinTreeNode<int> t,Queue<int> q)
        {
            Queue<int> q1 = new Queue<int>();
            return q1;
        }
        // הדפת ערכים ברמה מסויימת של העץ
        static void printValueOfFloor(BinTreeNode<int> t, int f)
        {
            if (t != null)
            {
                if (f == 0)
                {
                    Console.WriteLine(t.GetInfo());
                }
                else
                {
                    printValueOfFloor(t.GetRight(), f - 1);
                    printValueOfFloor(t.GetLeft(), f - 1);
                }
            }

        }
        // החזרת מספר צמתים ברמה מסויימת
        static int getFloorNumValues(BinTreeNode<int> t, int f)
        {
            if (t != null)
            {
                if (f == 0)
                {
                    return 1;
                }
                return (getFloorNumValues(t.GetLeft(), f - 1) + getFloorNumValues(t.GetRight(), f - 1));
            }
            return 0;
        }
        // קבלת ערך והדפסת הרמה הראשונה בה הוא מופיע
        static void printFloorByValue(BinTreeNode<int> t, int f, int level = 0)
        {
            if (t != null)
            {
                if (t.GetInfo() == f)
                {
                    Console.WriteLine(level);
                }
                printFloorByValue(t.GetLeft(), f, level + 1);
                printFloorByValue(t.GetRight(), f, level + 1);


            }

        }
        // הדפסה
        static void prePrint(BinTreeNode<int> t)
        {
            if (t != null)
            {

                Console.WriteLine(t.GetInfo());
                prePrint(t.GetLeft());
                prePrint(t.GetRight());
            }

        }
        // הדפסת בנים שמאליים בלבד
        public static void benSmol(BinTreeNode<int> t, bool smol = false)
        {
            if (t != null)
            {
                if (smol)
                {
                    Console.Write(t.GetInfo() + " ");

                }
                benSmol(t.GetLeft(), true);
                benSmol(t.GetRight(), false);

            }
        }
        // בדיקת גובה העץ
        public static int height(BinTreeNode<int> t)
        {
            if (t != null)
            {
                if (!hasSons(t))
                {
                    return 1;
                }
                return (Math.Max((height(t.GetLeft()) + 1), (height(t.GetRight()) + 1)));
            }
            return 0;

        }
        static bool hasRight(BinTreeNode<int> t)
        {
            return t.GetRight() != null;
        }
        static bool hasLeft(BinTreeNode<int> t)
        {
            return t.GetLeft() != null;
        }
        static bool hasSons(BinTreeNode<int> t)
        {
            return hasRight(t) || hasLeft(t);
        }
        // האם ערך קיים בעץ
        static bool valueExists(BinTreeNode<int> t, int m)
        {
            if (t != null)
            {
                if (t.GetInfo() == m)
                {
                    return true;
                }
                return ((valueExists(t.GetLeft(), m)) || valueExists(t.GetRight(), m));
            }
            else
            {
                return false;
            }
        }
        // הדפסה תוכית
        static void inPrint(BinTreeNode<int> t)
        {
            if (t != null)
            {
                inPrint(t.GetLeft());
                Console.Write(t.GetInfo() + " ");
                inPrint(t.GetRight());
            }

        }
        // הדפסה סופית
        static void sofPrint(BinTreeNode<int> t)
        {
            if (t != null)
            {
                sofPrint(t.GetLeft());
                sofPrint(t.GetRight());
                Console.WriteLine(t.GetInfo());
            }
        }
        //////////// מחסנית //////////////
        // פעולה של הפיכת מחסנית
        public static void DebugStack(Stack<int> s, int n)
        {
            Stack<int> tmp = CloneStack(s);// FlipStack(s); //!פעולה של הפיכת מחסנית, מופיע בדף
            while (!s.IsEmpty())
                s.Pop();
            while (!tmp.IsEmpty())
            {
                int x = tmp.Pop();
                if (x != n)
                    s.Push(x);
            }
        }
        // מיון
        public static Stack<int> sortnoarrays(Stack<int> UnSortedStack)
        {
            int x = howmuch(UnSortedStack);
            Stack<int> temp = CloneStack(UnSortedStack);
            Stack<int> temp1 = new Stack<int>();
            while(x!=0)
            {
                int maximum = findmax(temp);
                temp1.Push(maximum);
                DebugStack(UnSortedStack, maximum);
                temp = UnSortedStack;
                x--;
            }
            UnSortedStack = temp1;
            return temp1;
        }
        // מציאת ערך מקסימלי
         public static int findmax(Stack<int> UnSortedStack)
        {
            int max = 0;
            Stack<int> temp = CloneStack(UnSortedStack);
            while (!temp.IsEmpty())
            {
                int y=temp.Pop();
                if (y > max)
                {
                    max = y;
                }
            }
            return max;
        }
        // כמה איברים במחסנית
         public static int howmuch(Stack<int> random)//we check how much numbers/chars are in the stack
        {
            int count = 0;
            Stack<int> temp = CloneStack(random);
            while (!temp.IsEmpty())
            {
                temp.Pop();
                count++;

            }
            return count;
        }
        // העתקת מחסנית
        public static Stack<int> CloneStack(Stack<int> s)
        {
            Stack<int> newS = new Stack<int>();
            Stack<int> tmp = new Stack<int>();
            while (!s.IsEmpty())
                tmp.Push(s.Pop());
            while (!tmp.IsEmpty())
            {
                newS.Push(tmp.Top());
                s.Push(tmp.Pop());
            }
            return newS;
        }
        // מחיקת ערך ממחסנית
        static Stack<int> delete(Stack<int> p, int num)
        {
            Stack<int> a = p;
            Stack<int> newStack = new Stack<int>();
            int i = 0;
            int b = a.Pop();
            while (a.IsEmpty() == false)
            {
                if (b != num)
                {
                    newStack.Push(b);
                }
                else
                {
                    /* i++;
                     if (i > 0)
                     {
                         newStack.Push(num);
                     } */
                }
                b = a.Pop();

            }
            return newStack;
        }
        // מיון מחסנית
        static Stack<int> sort(Stack<int> m)
        {
            Stack<int> m1 = new Stack<int>();
            Stack<int> newM = new Stack<int>();
            int max = 0;

            while (m.IsEmpty() == false || m1.IsEmpty() == false)
            {
                Console.WriteLine("NEW: " + newM);
                while (m.IsEmpty() == false)
                {

                    m1.Push(m.Pop());
                    if (m1.Top() > max)
                    {
                        max = m1.Top();
                    }
                    Console.WriteLine("MAX: " + max);
                    Console.WriteLine(m);
                    Console.WriteLine(m1);
                }
                m1 = delete(m1, max);
                Console.WriteLine("AFTER DELETE:" + m1);
                newM.Push(max);
                Console.WriteLine("NEW: " + newM);

                while (m1.IsEmpty() == false)
                {

                    m.Push(m1.Pop());
                }
                Console.WriteLine(m);
                max = 0;
            }
            return newM;

        }
        // בדיקה האם ערך נמצא ברצף בתור
        public static bool bdika(Queue<int> q, int m)
        {
            Queue<int> p = new Queue<int>();
            int i = 0;
            p = cloneQueue(q);
            int a = q.Remove();
            while (p.IsEmpty() == false)
            {
                int b = p.Head();
                if (a == b && a == m)
                {
                    return true;
                }

                a = p.Remove();


            }
            return false;

        }
        // בדיקה האם ערך נמצא בתור
        public static bool exist(Queue<int> q, int m)
        {
            Queue<int> b = new Queue<int>();
            b = cloneQueue(q);
            while (!b.IsEmpty())
            {
                if (b.Remove() == m)
                {
                    return true;
                }

            }
            return false;
        }
        // מציאת מספר ערכים בין X לY בתור
        public static int getNumbersBetween(Queue<int> q, int low, int high)
        {
            int count = 0;
            Queue<int> m = cloneQueue(q);
            while (m.IsEmpty() == false)
            {
                int num = m.Remove();
                if (num >= low && num <= high)
                {
                    count++;
                }
            }
            return count;
        }
        // האם תור ממויין
        public static bool isSorted(Queue<int> q)
        {
            Queue<int> q1 = cloneQueue(q);
            int num = q1.Remove();
            if (num > q1.Head() || num == q1.Head())
            {
                // מהגדול לקטן
                while (q1.IsEmpty() == false)
                {

                    if (num < q1.Head())
                    {
                        return false;
                    }
                    num = q1.Remove();
                    Console.WriteLine(num);
                }
            }
            else
            {
                // מהקטן לגדול
                while (q1.IsEmpty() == false)
                {
                    if (num > q1.Head())
                    {
                        return false;
                    }
                    num = q1.Remove();
                    Console.WriteLine(num);
                }
            }
            return true;


        }
        // מציאת הערך המקסימלי בתור
        public static int getMax(Queue<int> q)
        {
            Queue<int> m = cloneQueue(q);
            int max = 0;
            while (m.IsEmpty() == false)
            {
                if (m.Head() > max)
                {
                    max = m.Head();
                }
                m.Remove();

            }
            return max;
        }
        // מציאת הערך המינימלי ביותר בתור
        public static int getMin(Queue<int> m)
        {
            Queue<int> p = new Queue<int>();
            p = cloneQueue(m);
            int min = p.Head();
            while (p.IsEmpty() == false)
            {
                if (min > p.Head())
                {
                    min = p.Head();
                }
                p.Remove();
            }

            return min;
        }
        //מחיקת כל הערכים השווים לערך מסויים מהתור
        public static Queue<int> delete(Queue<int> m, int s)
        {
            Queue<int> p = new Queue<int>();
            while (m.IsEmpty() == false)
            {
                if (m.Head() != s)
                {
                    p.Insert(m.Head());

                }
                m.Remove();
            }
            return p;
        }
        //החזרת תור ללא כפילויות מספרים
        public static Queue<int> kfilut(Queue<int> q)
        {
            Queue<int> m = new Queue<int>();
            while (q.IsEmpty() == false)
            {
                int num = q.Remove();
                if (exist(q, num) == false)
                {
                    m.Insert(num);
                }
            }
            return m;
        }
        //מיון תור עלייה
        public static Stack<int> ole(Queue<int> q)
        {
            Queue<int> p = new Queue<int>();
            Stack<int> s = new Stack<int>();
            p = cloneQueue(q);
            while (p.IsEmpty() == false)
            {
                int m = getMin(p);
                s.Push(m);
                p = delete(p, m);
            }
            return s;

        }
        // מיזוג תורים לתור אחד ממויין בסדר עולה
        public static Queue<int> bobo(Queue<int> q, Queue<int> q1)
        {
            Queue<int> s = new Queue<int>();
            int num;
            while (q1.IsEmpty() == false && q.IsEmpty() == false)
            {
                if (q.Head() > q1.Head())
                {
                    num = q.Remove();
                }
                else
                {
                    num = q1.Remove();
                }
                Console.WriteLine(num);
                s.Insert(num);
            }
            if (q1.IsEmpty())
            {
                while (q.IsEmpty() == false)
                {
                    s.Insert(q.Remove());
                }
            }
            else
            {
                while (q1.IsEmpty() == false)
                {
                    s.Insert(q1.Remove());
                }
            }
            return s;
        }
        // מיזוג תורים קלאסי
        public static Queue<int> Mizug(Queue<int> q, Queue<int> q1)
        {
            while (q1.IsEmpty() == false)
            {
                q.Insert(q.Remove());
                q.Insert(q1.Remove());
            }
            return q;

        }
        // אורך התור
        public static int LengthQueue(Queue<int> q)
        {
            int length = 0;
            Queue<int> qCopy = cloneQueue(q); //!
            while (!qCopy.IsEmpty())
            {
                length++;
                qCopy.Remove();
            }
            return length;
        }
        // קבלת ערך מסויים במקום מסויים בתור
        static int getValueInSpecificPlace(Queue<int> m, int place)
        {

            int i = 0;
            Queue<int> s = cloneQueue(m);
            while (s.IsEmpty() == false)
            {
                i++;
                if (i == place)
                {
                    return s.Head();
                }
                s.Remove();
            }
            return -999;
        }
        // קבלת מספר ערכים בתור
        static int getCount(Queue<int> m)
        {
            Queue<int> s = cloneQueue(m);
            int num = 0;
            while (s.IsEmpty() == false)
            {
                num++;
                s.Remove();
            }

            return num;
        }
        // סכום תור
        static int queueSum(Queue<int> m)
        {
            Queue<int> clone = cloneQueue(m);
            int sum = 0;
            while (clone.IsEmpty() == false)
            {
                sum = sum + clone.Remove();

            }
            return sum;

        }
        // העתקת תור
        static Queue<int> cloneQueue(Queue<int> q)
        {
            Queue<int> temp1 = new Queue<int>();
            Queue<int> temp2 = new Queue<int>();
            while (!q.IsEmpty())
            {
                temp1.Insert(q.Head());
                temp2.Insert(q.Remove());
            }
            while (!temp2.IsEmpty()) // החזרת התור למצבו המקורי
            {
                q.Insert(temp2.Remove());
            }
            return temp1;
        }
        /////////////// שרשרת חוליות /////////////

        public static Node<int> cloneNode(Node<int> temp)
        {
            Node<int> neww = new Node<int>(temp.GetInfo());
            Node<int> neww2 = new Node<int>(temp.GetInfo());
            neww2 = neww2.GetNext();
            while (neww2.GetNext() != null)
            {
                neww.SetNext(neww2);
                neww2 = neww2.GetNext();
            }
            return neww;

        }
        // טענת כניסה: הפעולה מקבלת רשימה של מספרים שלמים
        // טענת כניסה: הפעולה מחזירה את סכום כל איברי הרשימה
        // סיבוכיות זמן ריצה: O(n)
        public static int SumList(Node<int> l)
        {
            int sum = 0;
            Node<int> pos = l;
            while (pos != null)
            {
                sum += pos.GetInfo();
                pos = pos.GetNext();
            }
            return sum;
        }
        // טענת כניסה: הפעולה מקבלת רשימה של מספרים שלמים
        // טענת יציאה: הפעולה מחזירה את אורך הרשימה - מספר החוליות בה
        // סיבוכיות זמן ריצה: O(n)
        public static int LengthList(Node<int> l)
        {
            int length = 0;
            Node<int> pos = l;
            while (pos != null)
            {
                length++;
                pos = pos.GetNext();
            }
            return length;
        }
        // טענת כניסה: הפעולה מקבלת רשימה של מספרים שלמים ומספר שלם
        // טענת יציאה: הפעולה מחזירה את מספר הפעמים שהמספר מופיע ברשימה
        // סיבוכיות זמן ריצה: O(n)
        public static int HowManyList(Node<int> l, int n)
        {
            int count = 0;
            Node<int> pos = l;
            while (pos != null)
            {
                if (pos.GetInfo() == n)
                    count++;
                pos = pos.GetNext();
            }
            return count;
        }

        // טענת כניסה: הפעולה מקבלת רשימה של מספרים שלמים
        // טענת יציאה: הפעולה מחזירה "אמת" אם הרשימה ממוינת בסדר עולה, אחרת מחזירה "שקר"
        // סיבוכיות זמן ריצה: O(n)
        public static bool IsSorted(Node<int> l)
        {
            Node<int> pos = l;
            while (pos.GetNext() != null)
            {
                if (pos.GetInfo() > pos.GetNext().GetInfo())
                    return false;
                pos = pos.GetNext();
            }
            return true;
        }
        // מחיקת חוליה מהשרשרת
        public static Node<int> delete(Node<int> p, Node<int> n)
        {
            Node<int> s = p;
            while (p != null)
            {
                if (p.GetNext() == n)
                {
                    p.SetNext(n.GetNext());
                }
                p = p.GetNext();
            }

            return s;
        }
        // ניגודים בשרשרת חוליות
        public static Node<int> nigud(Node<int> n)
        {
            Node<int> p = n;
            bool fuck = false;
            while (n != null)
            {
                if (n.GetInfo() != 0)
                {
                    int m = n.GetInfo() * -1;
                    n.SetNext(new Node<int>(m, n.GetNext()));
                    fuck = true;
                }
                else
                {
                    if (p == n)
                    {
                        p = n.GetNext();
                    }
                    else
                    {
                        delete(p, n);
                    }
                }
                if (!fuck)
                {
                    n = n.GetNext();

                }
                else
                {
                    n = n.GetNext().GetNext();
                }
                fuck = false;
            }
            return p;
        }

        ////////// מחסנית ////////////
        // היפוך מחסנית
        public static Stack<int> FlipStack(Stack<int> s)
        {
            Stack<int> newS = new Stack<int>();
            Stack<int> tmp = CloneStack(s); //!
            while (!tmp.IsEmpty())
                newS.Push(tmp.Pop());
            return newS;
        }



        // עדכון המחסנית לרצף המספרים הארוך ביותר
        static void getOnlyRezef(Stack<int> stk)
        {
            int i = 1;
            int max = 1;
            int j = 0, place = 1;
            Stack<int> p = CloneStack(stk);
            Stack<int> copy = CloneStack(stk);
            Stack<int> s = new Stack<int>();
            int num = p.Pop();
            bool fuck = false;
            // רק עלייה
            // כדי לבצע ירידה צריך לבדוק את ההפרש הראשוני בכל רצף ולהשוות את ההפרשים הבאים אליו
            while (p.IsEmpty() == false)
            {
                place++;
                if (p.Top() - num == -1)
                {

                    i++;
                    Console.WriteLine("MY I:" + i);
                    Console.WriteLine(p.Top());
                }
                else
                {

                    if (i > max)
                    {
                        max = i;
                        j = place - max;

                    }
                    i = 1;

                }

                num = p.Pop();
                if (p.IsEmpty() == true)
                {

                    if (i > max)
                    {
                        max = i;
                        j = place - max + 1;
                    }
                }
            }
            Console.WriteLine("i:" + max);
            Console.WriteLine("j:" + j);
            if (j != 0)
            {
                // J => מיקום התחלת הרצף
                // MAX => מספר איברי הרצף
                int pogi = 0;
                bool done = false;
                while (copy.IsEmpty() == false)
                {
                    pogi++;
                    if (pogi == j)
                    {

                        while (max != 0)
                        {

                            s.Push(copy.Top());
                            Console.WriteLine(copy.Pop());
                            max--;


                        }
                        done = true;

                    }
                    if (!done)
                    {
                        copy.Pop();
                    }
                }
                Console.WriteLine(s);
            }
            else
            {
                Console.WriteLine("NO REZEF");
            }

        }
        // ניקוי מחסנית
        static Stack<int> clean(Stack<int> s)
        {
            while (s.IsEmpty() == false)
            {
                s.Pop();
            }
            return s;

        }