using System;

using System.Collections.Generic;

public class Program

{   

    /*public class LinkedListNode<T>{

        public T Value {get;set;}

        public LinkedListNode<T> Next;

        public LinkedListNode(T val, LinkedListNode<T> next=null){

            this.Value = val;

            this.Next = next;   

        }

    }*/

    public static void PrintLinkedList<T>(LinkedListNode<T> node){

        if (node==null) return;

        while (node!=null){

            Console.Write(node.Value + " ");

            node=node.Next;

        }

        Console.WriteLine();

    }

    public class TreeNode<T>{

        public T Data {get; set;}

        public TreeNode<T> Left {get; set;}

        public TreeNode<T> Right {get; set;}

        public TreeNode(T data){

            this.Data = data;

        }

        public void PrintPretty(string indent="", bool last=true){

            Console.Write(indent);

            if (last) {

                Console.Write("\\-");

                indent += "  ";

            }

            else {

                Console.Write("|-");

                indent += "| ";

            }

            Console.WriteLine(Data);

            if (Left == null && Right == null) return;

            if (Left != null){

                Left.PrintPretty(indent, false);

            }

            if (Right != null){

                Right.PrintPretty(indent, true);

            }

         } 

    }

    public static TreeNode<int> CreateTestTree(){

        var rootNode = new TreeNode<int>(1){

            Left = new TreeNode<int>(2){

                Left = new TreeNode<int>(4),

                Right = new TreeNode<int>(5){

                    Left = new TreeNode<int>(8),

                    Right = new TreeNode<int>(9){

                        Left = new TreeNode<int>(11)

                    }

                }

            },

            Right = new TreeNode<int>(3){

                Left = new TreeNode<int>(6),

                Right = new TreeNode<int>(7){

                    Left = new TreeNode<int>(10)

                }

            }

        };

        return rootNode;

    }

    private static void CreateLinkedListsOfDepths<T>(TreeNode<T> node, int depth, List<LinkedList<T>> listOfDepths){

        if (node==null) return;

        var newElement = new LinkedListNode<T>(node.Data);

        LinkedList<T> depthList = null;

        if (listOfDepths.Count>depth){

            depthList = listOfDepths[depth];

        }

        else {

            depthList =  new LinkedList<T>();

            listOfDepths.Add(depthList);

            /*Levels are always traversed in order. So, if this is the first time we've

             visited level i, we must have seen levels 0 through i - 1. We can

            therefore safely add the level at the end. */

​

        }

        depthList.AddLast(newElement);

        CreateLinkedListsOfDepths<T>(node.Left, depth+1, listOfDepths);

        CreateLinkedListsOfDepths<T>(node.Right, depth+1, listOfDepths);

    }

    public static List<LinkedList<T>> ListOfDepths<T>(TreeNode<T> root){    

        var listOfDepths = new List<LinkedList<T>>();

        var depth = 0;

        CreateLinkedListsOfDepths(root, depth, listOfDepths);

        return listOfDepths;

    }

    public static void Main()

    {

        Console.WriteLine("Hello World");

        var root = CreateTestTree();

        root.PrintPretty("",true);

        var listOfDepths = ListOfDepths(root);

        var depth = 0;

        foreach (var element in listOfDepths){

            Console.Write(depth + ": ");

            PrintLinkedList(element.First);

            depth++;

        }

    }

}