Recursive menu is wrong level ordered

Question

Trying to build recursive menu with C#. The menu I need is as follows:

. Clients
. . . . Client 1
. . . . Client 3
. Company
. . . . Vision
. . . . . . . Short Statement
. . . . Who We Are
. . . . . . . Contact Us
. . . . . . . Team
. . . . . . . . . . Write To Us
. . . . . . . . . . . . . Media

But I'm getting:

. Company
. . . . Vision
. . . . Who We Are
. . . . . . . Short Statement
. . . . . . . . . . Contact Us
. . . . . . . . . . Team
. . . . . . . . . . . . . Write To Us
. . . . . . . . . . . . . . . . Media
. Clients
. . . . Client 1
. . . . Client 3

Some corrections need to be done so I need your help:

• Menu items should be ordered alphabetically; ex. Clients should be first then Company
• Some items are wrong level ordered and indented; ex. Short Statement should be after Vision and before Who We Are

So far I tried:

class Program
{
    public class Node<T>
    {
        public T Data { get; set; }
        public List<Node<T>> Children { get; set; }

        public Node()
        {
            Children = new List<Node<T>>();
        }


        public List<Node<T>> LevelOrder()
        {
            List<Node<T>> list = new List<Node<T>>();
            Queue<Node<T>> queue = new Queue<Node<T>>();
            queue.Enqueue(this);
            while (queue.Count != 0)
            {
                Node<T> temp = queue.Dequeue();
                foreach (Node<T> child in temp.Children)
                    queue.Enqueue(child);
                list.Add(temp);
            }
            return list;
        }

        public List<Node<T>> PreOrder()
        {
            List<Node<T>> list = new List<Node<T>>();
            list.Add(this);
            foreach (Node<T> child in Children)
                list.AddRange(child.PreOrder());
            return list;
        }

        public List<Node<T>> PostOrder()
        {
            List<Node<T>> list = new List<Node<T>>();
            foreach (Node<T> child in Children)
                list.AddRange(child.PreOrder());
            list.Add(this);
            return list;
        }
    }

    public class Entity
    {
        public int id { get; set; }
        public string menuName { get; set; }
        public int? parentID { get; set; }
        public bool isHidden { get; set; }
        public string linkURL { get; set; }
    }
    static void Main(string[] args)
    {
        var data = @"ID;MenuName;ParentID;isHidden;Link
1;Company;NULL;False;/company
2;Who We Are;1;False;/company/whoweare
3;Vision;1;False;/company/vision
4;Team;2;False;/company/whoweare/team
5;Client 3;10;False;/clients/client3
6;Client 1;10;False;/clients/client1
7;Client 4;10;True;/clients/client4
8;Client 5;10;True;/clients/client5
10;Clients;NULL;False;/clients
11;Contact Us;2;False;/company/whoweare/contactus
12;Write To Us;4;False;/company/whoweare/team/writetous
13;Media;12;False;/company/whoweare/team/writetous/media
14;Short Statement;3;False;/company/vision/shortstatement";

        var lines = data.Split('\n');
        var rootNodes = new List<Node<Entity>>();
        var childItems = new List<Entity>();

        foreach (var row in lines.Skip(1))
        {
            var columns = row.Split(';');

            var id = Convert.ToInt32(columns[0]);
            var menuName = columns[1];
            var parentID = ToNullableInt(columns[2]);
            var isHidden = Convert.ToBoolean(columns[3]);
            var linkURL = columns[4];

            var entity = new Entity()
            {
                id = id,
                menuName = menuName,
                parentID = parentID,
                isHidden = isHidden,
                linkURL = linkURL
            };

            if (parentID == null)
            {
                rootNodes.Add(new Node<Entity>()
                {
                    Data = entity
                });
            }
            else
            {
                childItems.Add(entity);
            }
        }


        foreach (var rootNode in rootNodes)
        {
            foreach (var childItem in childItems.OrderBy(a => a.parentID).ThenBy(b => b.menuName))
            {
                var newNode = new Node<Entity>()
                {
                    Data = childItem
                };

                Insert(rootNode, newNode);
            }
        }

        foreach (var rootNode in rootNodes)
        {
            var indent = 0;
            var previous = rootNode;
            foreach (var node in rootNode.LevelOrder())
            {
                if (node.Data.isHidden) continue;

                if (previous.Data.parentID != node.Data.parentID)
                    indent++;

                for (var i = 0; i < indent; i++)
                    Console.Write(". . . ");

                Console.WriteLine(". " + node.Data.menuName);
                previous = node;
            }
        }
    }

    public static void Insert(Node<Entity> rootNode, Node<Entity> targetNode)
    {
        foreach (var current in rootNode.LevelOrder())
        {
            if (current.Data.id == targetNode.Data.parentID)
            {
                current.Children.Add(targetNode);
                return;
            }
        }
    }

    public static int? ToNullableInt(string s)
    {
        int i;
        if (int.TryParse(s, out i)) return i;
        return null;
    }
}

Answer 1

If you update the PreOrder to work with a tuple of (level, item) like:

        public List<(int level, Node<T> item)> PreOrder(int level = 0)
        {
            List<(int level, Node<T> item)> list = new List<(int level, Node<T> item)>();
            list.Add((level, this));
            level += 1;
            foreach (Node<T> child in Children)
                list.AddRange(child.PreOrder(level));
            return list;
        }

and use it in your print section like (I have also added the order by menuName here):

        foreach (var rootNode in rootNodes.OrderBy(a => a.Data.menuName))
        {
            var indent = 0;
            foreach (var node in rootNode.PreOrder())
            {
                if (node.item.Data.isHidden)
                    continue;

                for (var i = 0; i < node.level; i++)
                    Console.Write(". . . ");

                Console.WriteLine(". " + node.item.Data.menuName);
            }
        } 

that will return the menu in the same format that you have requested.