using System;

using System.Collections.Generic;

using System.Linq;

​

class Program

{

 /*

    Please print the menu tree on Console. 

    Each nested level should be shifted from the parent on 4 stars '*'. 

    The order of same-level items should be the same as the order in the original list.

    <c>-1</c> indicates the root level. At least one root level will always be present.

​

    Please see the sample output:

    Printed menu:

    Menu1

    Menu2

    ****Menu4

    ********Menu5

    Menu3

    ****Menu8

    ********Menu6

    ********Menu7

    */

​

    private static readonly IList<Menu> MenuItems = new List<Menu>

    {

        new Menu(1, -1, "Menu1"),

        new Menu(2, -1, "Menu2"),

        new Menu(3, -1, "Menu3"),

        new Menu(4, 2, "Menu4"),

        new Menu(5, 4, "Menu5"),

        new Menu(6, 8, "Menu6"),

        new Menu(7, 8, "Menu7"),

        new Menu(8, 3, "Menu8"),

    };

​

    class Menu

    {

        public Menu(int id, int parentId, string name)

        {

            Id = id;

            ParentId = parentId;

            Name = name;

        }

​

        public int Id { get; }

        public int ParentId { get; }

        public string Name { get; }

    }

​

    public static void Main()

    {

        Console.WriteLine("Printed menu:");

        PrintMenu(MenuItems);

    }

​

    private static void PrintMenu(IEnumerable<Menu> menuItems)

    {

        var indent = "****";

        var vistedItems = new List<int>();

        var menuItemsDic = menuItems.ToDictionary(item => item.Id, subItems => new List<Menu>());

​

        foreach (var item in menuItems)

        {

            if (item.ParentId == -1)

                continue;

​

            List<Menu> subItems;

            if (menuItemsDic.TryGetValue(item.ParentId, out subItems))

            {

                menuItemsDic[item.ParentId].Add(item);

            }

        }

​

​

        foreach (var item in menuItems)

        {

            if (item.ParentId == -1)

                PrintSubItems(item, 0);

        }

​

        void PrintSubItems(Menu item, int level)

        {

            //TODO: Check for circular dependency if required.

            Console.WriteLine(string.Concat(Enumerable.Repeat(indent, level)) + item.Name);

            List<Menu> subItems = new List<Menu>();

            if (menuItemsDic.TryGetValue(item.Id, out subItems))

            {

                foreach (var subItem in subItems)

                {

                    PrintSubItems(subItem, level + 1);

                }

            }

        }

    }

}