Unwrapping nested lists into a flat list?

Question

I store a series of objects into the database that have a pretty simple structure. Represented as a model, they looks similar to

public SiteMenuItem 
{
    public int Id {get;set;}
    public string Name {get;set;}
    public int? ParentId {get;set;}
    public int? Order {get;set;}

    public virtual List<SiteMenuItem> Children {get;set;} //null on initialization 
}

When I retrieve these values from the database, I transform these values into a nested-list tree-like structure for use in our web-app. I do that in a fashion similar to:

private static List<SiteMenuItem> GetChildren(List<SiteMenuItem> menu)
{
    // For every SiteMenuItem with a parentId, place the child under their parent.
    menu.ForEach(menuItem => menuItem.Children = menu.Where(n => n.ParentId == menuItem.Id).ToList());
    // Remove all orphaned items.
    menu.RemoveAll(n => n.ParentId != null);

    return menu;
}

This function works great for transforming my flat list into a list of hierarchical items. However, I'm attempting to figure out how to do the reverse.

I need to figure out how to traverse the list of items (possibly recursively?) and return them to a flat list of items with the ParentId properly populated.

What is the best way to do this?

Edit

The problem becomes even more complicated as I need to also track the order in which the items are stored. For example given the following hierarchy, I need to set the proper ordering.

The following objects:

[  
   {  
      "Id":1,
      "Name":"Menu Item 1",
      "Children":[  
         {  
            "Id":2,
            "Name":"Sub Menu Item 1",
            "Children":[  

            ]
         },
         {  
            "Id":3,
            "Name":"Sub Menu Item 2",
            "Children":[  

            ]
         }
      ]
   },
   {  
      "Id":4,
      "Name":"Menu Item 2",
      "Children":[  

      ]
   },
   {  
      "Id":5,
      "Name":"Menu Item 3",
      "Children":[  
         {  
            "Id":6,
            "Name":"Sub Menu Item 1",
            "Children":[  
               {  
                  "Id":7,
                  "Name":"Sub Menu Item 2"
               }
            ]
         },
         {  
            "Id":8,
            "Name":"Sub Menu Item 1",
            "Children":[  

            ]
         }
      ]
   }
]

Would be transformed into:

[  
   {  
      "Id":1,
      "Name":"Menu Item 1",
      "Parent":"",
      "Order":1
   },
   {  
      "Id":2,
      "Name":"Sub Menu Item 1",
      "Parent":1,
      "Order":1
   },
   {  
      "Id":3,
      "Name":"Sub Menu Item 2",
      "Parent":1,
      "Order":2
   },
   {  
      "Id":4,
      "Name":"Menu Item 2",
      "Parent":"",
      "Order":2
   },
   {  
      "Id":5,
      "Name":"Menu Item 3",
      "Parent":"",
      "Order":3
   },
   {  
      "Id":6,
      "Name":"Sub Menu Item 1",
      "Parent":5,
      "Order":1
   },
   {  
      "Id":7,
      "Name":"Sub Sub Menu Item 1",
      "Parent":6,
      "Order":1
   },
   {  
      "Id":8,
      "Name":"Sub Menu Item 2",
      "Parent":5,
      "Order":2
   }
]

Visually the menu would look at such

Menu Item 1 | Menu Item 2 | Menu Item 3
     |                           |
Sub1 - Sub2                 Sub1 - Sub2
                              /
                          SubSub1      

The children should effectively always know their order within the original lists (arrays).

EDIT 2

I created a modified solution based off the linked [DUPLICATE] that allows me to maintain the proper ordering (albeit in a slightly different fashion) and it allows me to track the proper parents of each node.

public static IEnumerable<SiteMenuItemEditViewModel> FlattenItems(IEnumerable<SiteMenuItemEditViewModel> parents)
{
    var stack = new Stack<SiteMenuItemEditViewModel>();
    var order = 0;

    foreach (var item in parents.Reverse())
    {
        item.parentId = null;
        stack.Push(item);
    }

    while (stack.Count > 0)
    {
        var current = stack.Pop();

        current.order = order;
        current.menuItems.Reverse();

        yield return current;

        foreach (var child in current.children)
        {
            child.parentId = current.id;
            stack.Push(child);
        }

        order++;
    }
}