using System;

using System.Collections.Generic;

public class Program

{

    public static void Main()

    {

        Node root = BuildTree();

        PrintLevelOrder(root);

        Console.WriteLine("\n-------\n");

        PrintLevelsLineByLine(root);

    }

    public static Node BuildTree(){

        Node one = new Node(1);

        Node two = new Node(2);

        Node three = new Node(3);

        Node four = new Node(4);

        Node five = new Node(5);

        Node six = new Node(6);

        Node seven = new Node(7);

        Node eight = new Node(8);

        one.left = two;

        one.right = three;

        two.left = four;

        three.left = five;

        three.right = six;

        six.left = seven;

        seven.right = eight;

        return one;

    }

    //http://www.geeksforgeeks.org/print-level-order-traversal-line-line/

    public static void PrintLevelsLineByLine(Node n){

        // base case

        if(n == null) return;

        int depth = 0;

        Queue<Node> q = new Queue<Node>();

        q.Enqueue(n);

        while(q.Count>0){

            int nodeCount = q.Count;

            if(nodeCount == 0) break;

            if(depth == 0)

                Console.WriteLine(";{0}#ROOT#{1}", depth, q.Peek().data);

            depth++;

            // deque all nodes at current level and enque next level

            while(nodeCount > 0){

                Node cur = q.Dequeue();

                if(cur.left != null){

                    Console.WriteLine(";{0}#L#{1}", depth, cur.left.data);

                    q.Enqueue(cur.left);    

                }

                if(cur.right != null){

                    Console.WriteLine(";{0}#R#{1}", depth,  cur.right.data);

                    q.Enqueue(cur.right);   

                }

                nodeCount--;

            }

            Console.WriteLine();

        }

    }

    //http://www.geeksforgeeks.org/level-order-tree-traversal/

    public static void PrintLevelOrder(Node root) 

    {

        Queue<Node> queue = new Queue<Node>();

        queue.Enqueue(root);

        int depth = 0;

        while (queue.Count > 0) 

        {           

            /* dequee() removes the present head. */

            Node tempNode = queue.Dequeue();

            if(depth == 0)

                Console.WriteLine(";{0}#ROOT#{1}", depth, tempNode.data);

            depth++;

            /*Enqueue left child */

            if (tempNode.left != null) {

                Console.WriteLine(";{0}#L#{1}", depth, tempNode.left.data);

                queue.Enqueue(tempNode.left);

            }else{

                //Console.WriteLine(";{0}#L#NULL", depth);

            }

            /*Enqueue right child */

            if (tempNode.right != null) {

                Console.WriteLine(";{0}#R#{1}", depth,  tempNode.right.data);

                queue.Enqueue(tempNode.right);

            }else{

                //Console.WriteLine(";{0}#R#NULL", depth);

            }

        }

    }

    public class Node{

        public Node left;

        public Node right;

        public int data;

        public Node(int d){

            data = d;   

        }

    }

}