Upside-Down Tree - Part 2 of 2

Apart from the O(nlogn) solution, the three solutions shown below are all O(n)-time and O(n)-space. They all have pros and cons:

1) Use a priority queue: the idea is similar to a BFS but instead of using a regular queue use a priority queue. To enqueue the elements use DFS. Make sure that the lower nodes have higher priority than the upper nodes. There is some weird calculation that needs to happen in order to ensure the elements are printed in the right order (say left to right), hence due to that I don't personally recommend this solution.

2) Revert the tree. This is a fun solution because you get to revert the pointers of the tree and then do a simple BFS. The reversion is a neat way to handle the pointers of the tree (btw, you need a DFS for that). The drawback is the alteration of the tree structure.

3) Use a queue and stack. This to me is an elegant solution: do a BFS just like if you were to going to print the tree level by level. Instead of printing, though, push into a stack. After that, simply traverse the stack and print the elements. Bonus points for not needing recursion (the other ones you don't necessarily need recursion either, but the solution here in (3) is straight up non recursively).

Code is below, hope you enjoy! MDB

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

namespace PrintTreeUpSideDown
{
    class Program
    {
        static void Main(string[] args)
        {
            /*
             *             1
             *       2               3
             *   4       5      6        7
             * a   b   c   d   e f     g   h
             * 
             */

            Tree tree = new Tree('1');
            tree.left = new Tree('2');
            tree.right = new Tree('3');
            tree.left.left = new Tree('4');
            tree.left.right = new Tree('5');
            tree.right.left = new Tree('6');
            tree.right.right = new Tree('7');
            tree.left.left.left = new Tree('a');
            tree.left.left.right = new Tree('b');
            tree.left.right.left = new Tree('c');
            tree.left.right.right = new Tree('d');
            tree.right.left.left = new Tree('e');
            tree.right.left.right = new Tree('f');
            tree.right.right.left = new Tree('g');
            tree.right.right.right = new Tree('h');

            Console.WriteLine("Solution based on Priority Queues:");
            PrintUpSideDownTreeWithPriorityQueue(tree);

            Console.WriteLine();
            Console.WriteLine();

            Console.WriteLine("Solution based on Queue and Stack:");
            PrintUpSideDownTreeWithStack(tree);

            Console.WriteLine();
            Console.WriteLine();

            Console.WriteLine("Solution based on reversing the tree:");
            PrintUpSideDownTreeByReversing(tree);
        }

        static void PrintUpSideDownTreeByReversing(Tree tree)
        {
            LinkedList<Tree> listOfLeaves = new LinkedList<Tree>();

            RevertTree(null, tree, listOfLeaves);

            Queue queue = new Queue();
            foreach (Tree leaf in listOfLeaves)
            {
                QueuedItem qi = new QueuedItem();
                qi.tree = leaf;
                qi.level = 1;
                queue.Enqueue(qi);
            }

            Hashtable htVisitedNode = new Hashtable();
            int currentLevel = -1;
            string spaces = "";
            while (queue.Count > 0)
            {
                QueuedItem qi = (QueuedItem)queue.Dequeue();
                if (currentLevel == -1)
                {
                    currentLevel = qi.level;
                    Console.Write("{0}{1} ", spaces, qi.tree.value);
                    spaces += "**";
                }
                else if (qi.level != currentLevel)
                {
                    Console.WriteLine();
                    spaces += "*";
                    currentLevel = qi.level;
                    Console.Write("{0}{1} ", spaces, qi.tree.value);
                }
                else
                {
                    Console.Write("{0} ", qi.tree.value);
                }

                if (qi.tree.right != null && !htVisitedNode.ContainsKey(qi.tree.right))
                {
                    htVisitedNode.Add(qi.tree.right, true);
                    QueuedItem nqi = new QueuedItem();
                    nqi.tree = qi.tree.right;
                    nqi.level = qi.level + 1;
                    queue.Enqueue(nqi);
                }
            }
        }

        static void RevertTree(Tree parentNode,
                               Tree currentNode, 
                               LinkedList<Tree> listOfLeaves)
        {
            if (currentNode == null) return;

            if (currentNode.left == null && currentNode.right == null) //Leaf
            {
                currentNode.right = parentNode;
                listOfLeaves.AddLast(currentNode);
            }
            else
            {
                Tree tempLeft = currentNode.left;
                Tree tempRight = currentNode.right;

                currentNode.right = parentNode;
                currentNode.left = null;

                RevertTree(currentNode, tempLeft, listOfLeaves);
                RevertTree(currentNode, tempRight, listOfLeaves);
            }
        }

        static void PrintUpSideDownTreeWithStack(Tree tree)
        {
            if (tree == null) return;

            Queue<QueuedItem> queue = new Queue<QueuedItem>();
            Stack<QueuedItem> stack = new Stack<QueuedItem>();

            QueuedItem qi = new QueuedItem();
            qi.tree = tree;
            qi.level = 1;
            queue.Enqueue(qi);

            while (queue.Count > 0)
            {
                qi = (QueuedItem)queue.Dequeue();
                stack.Push(qi);

                if (qi.tree.right != null)
                {
                    QueuedItem nqi = new QueuedItem();
                    nqi.tree = qi.tree.right;
                    nqi.level = qi.level + 1;
                    queue.Enqueue(nqi);
                }
                if (qi.tree.left != null)
                {
                    QueuedItem nqi = new QueuedItem();
                    nqi.tree = qi.tree.left;
                    nqi.level = qi.level + 1;
                    queue.Enqueue(nqi);
                }
            }

            int currentLevel = -1;
            string spaces = "";
            while (stack.Count > 0)
            {
                qi = (QueuedItem)stack.Pop();
                if (currentLevel == -1)
                {
                    currentLevel = qi.level;
                    Console.Write("{0}{1} ", spaces, qi.tree.value);
                    spaces += "..";
                }
                else if (qi.level != currentLevel)
                {
                    Console.WriteLine();
                    spaces += ".";
                    currentLevel = qi.level;
                    Console.Write("{0}{1} ", spaces, qi.tree.value);
                }
                else
                {
                    Console.Write("{0} ", qi.tree.value);
                }
            }
        }

        static void PrintUpSideDownTreeWithPriorityQueue(Tree tree)
        {
            PriorityQueue pq = new PriorityQueue(1000, true);
            int index = 1;
            AddTreeToPriorityQueue(tree, 1, ref index, pq);

            int currentLevel = -1;
            string spaces = "";
            while (pq.Count > 0)
            {
                QueuedItem qi = (QueuedItem)pq.Dequeue();
                if (currentLevel == -1)
                {
                    currentLevel = qi.level / 100;
                    Console.Write("{0}{1} ", spaces, qi.tree.value);
                    spaces += "  ";
                }
                else if ((qi.level / 100) != currentLevel)
                {
                    Console.WriteLine();
                    spaces += " ";
                    currentLevel = qi.level / 100;
                    Console.Write("{0}{1} ", spaces, qi.tree.value);
                }
                else
                {
                    Console.Write("{0} ", qi.tree.value);
                }
            }
        }

        static void AddTreeToPriorityQueue(Tree t, 
                                           int level,
                                           ref int index,
                                           PriorityQueue pq)
        {
            if (t == null) return;

            QueuedItem qi = new QueuedItem();
            qi.tree = t;
            qi.level = level + index;
            pq.Enqueue(qi, qi.level);

            index++;
            AddTreeToPriorityQueue(t.right, 100 * level, ref index, pq);

            index++;
            AddTreeToPriorityQueue(t.left, 100 * level, ref index, pq);
        }
    }

    class QueuedItem
    {
        public Tree tree = null;
        public int level = -1;
    }

    class Tree
    {
        public char value;
        public Tree left = null;
        public Tree right = null;

        public Tree(char value)
        {
            this.value = value;
            this.left = null;
            this.right = null;
        }
    }

    /*By-the-book PriorityQueue*/
    public class PriorityQueue
    {
        public struct HeapEntry
        {
            private object item;
            private long priority;
            public HeapEntry(object item, long priority)
            {
                this.item = item;
                this.priority = priority;
            }
            public object Item
            {
                get
                {
                    return item;
                }
            }
            public long Priority
            {
                get
                {
                    return priority;
                }
            }
        }

        private long count;
        private long capacity;
        private bool descending; //Means that the max element at the top
        private HeapEntry[] heap;

        public long Count
        {
            get
            {
                return this.count;
            }
        }

        public PriorityQueue(long capacity, bool descending)
        {
            this.capacity = capacity;
            this.descending = descending;
            heap = new HeapEntry[this.capacity];
        }

        public object Dequeue()
        {
            object result = heap[0].Item;
            count--;
            trickleDown(0, heap[count]);
            return result;
        }

        public void Enqueue(object item, long priority)
        {
            count++;
            bubbleUp(count - 1, new HeapEntry(item, priority));
        }

        private void bubbleUp(long index, HeapEntry he)
        {
            long parent = (index - 1) / 2;
            // note: (index > 0) means there is a parent
            while (
                   (index > 0) &&
                   ((this.descending && heap[parent].Priority < he.Priority) || (!this.descending && heap[parent].Priority > he.Priority))
                  )
            {
                heap[index] = heap[parent];
                index = parent;
                parent = (index - 1) / 2;
            }
            heap[index] = he;
        }

        private void trickleDown(long index, HeapEntry he)
        {
            long child = (index * 2) + 1;
            while (child < count)
            {
                if (
                    ((child + 1) < count) &&
                    ((this.descending && heap[child].Priority < heap[child + 1].Priority) || (!this.descending && heap[child].Priority > heap[child + 1].Priority))
                   )
                {
                    child++;
                }
                heap[index] = heap[child];
                index = child;
                child = (index * 2) + 1;
            }
            bubbleUp(index, he);
        }
    }
}