Restructure an XML tree based on sequence of elements with "ID" and "parent ID"

Question

What I want to happen is that I want to put inside the element whose ID is equal to ParentID? So like in my example the Group whose ParentId=1 should be inside the Group whose Id=1 How can I possibly do this? Got so confused..

As of now here is my code:

XElement xroot = new XElement("Root");
        XElement xnavigations = null;
        XElement xmenus = null;

        foreach (DataRow navigations in GetNavigationSets().Rows)
        {
            xnavigations = new XElement("Group", 
                new XElement("GroupName", navigations["name"].ToString())
                );
            xnavigations.SetAttributeValue("Id", navigations["id"].ToString());
            xnavigations.SetAttributeValue("ParentId", navigations["parent_id"].ToString());

            foreach (DataRow menus in GetMenusInNavigationSetByNavigation(int.Parse(navigations["id"].ToString())).Rows)
            {
                foreach (DataRow menu in GetMenuById(int.Parse(menus["menu_id"].ToString())).Rows)
                {
                    xmenus = new XElement("Menu", 
                        new XElement("Name", menu["name"].ToString()),
                        new XElement("Price", menu["price"].ToString()),
                        new XElement("Description", menu["description"].ToString())
                        );

                    xnavigations.Add(xmenus);
                }
            }

            xroot.Add(xnavigations);
        }

        xroot.Save("main.xml");

New output:

Answer 1

Here is a mutating approach and it relies upon side-effects. It's not as clean as recursion and re-building, but it is often "sufficient". And, it's pretty darn easy to write.

Input "XML":

var root = XElement.Parse(@"<root>
<group id='1' />
<group id='4' parent='2' />
<group id='2' parent='1' />
<group id='3' parent='2' />
<group id='5' />
</root>");

Turn into tree:

// So we can find parent by ID
var groupMap = root.Elements("group")
  .ToDictionary(e => (string)e.Attribute("id"), e => e);

// ToList so we don't iterate modified collection
foreach (var e in root.Elements().ToList()) {
  XElement parent;
  if (groupMap.TryGetValue((string)e.Attribute("parent") ?? "", out parent)) {
     // Unlike standard XML DOM,
     // make sure to remove XElement from parent first
     e.Remove();
     // Add to correct parent
     parent.Add(e);
  }
}

// LINQPad :-)
// root.Dump();

Output XML:

<root>
  <group id="1">
    <group id="2" parent="1">
      <group id="4" parent="2" />
      <group id="3" parent="2" />
    </group>
  </group>
  <group id="5" />
</root>