A complex selection LINQ query I am stuck on recursive selection of the objects for TreeView.

I have some class IMenuDataSet, that stores objects, named 'I' in the List property:

public partial class IMenuDataSet
{
    private List&lt;I&gt; itemsField = new List&lt;I&gt;(); 


Each 'I' object has XDocument doc and public IT[] T properties:

public partial class I
{

    [System.Xml.Serialization.XmlIgnoreAttribute()]
    public XDocument doc;
    public IT[] T


And IT object is

public partial class IT
{

    private string nField;

    private string valueField;


IT object is a part of serialized XML, that could looks like 

&lt;?xml version="1.0" encoding="UTF-8"?&gt;
&lt;I c="PieMenuCategory" i="pie_menu_category" m="abc" n="someM" s="16312547127249792256"&gt;
  &lt;T n="_collapsible"&gt;False&lt;/T&gt;
  &lt;T n="_display_name"&gt;0x3F70BCAA&lt;/T&gt;  
  &lt;T n="_parent"&gt;12342647638224932948&lt;/T&gt;
&lt;/I&gt;


An important note: each XML file (each IT object) has s attribute, the value of this attribute is ID of the I tag (IT object). 
ID of the parent element stored in T tag, that has attribute n="_parent" .
Each main (top/root) hasn't such &lt;T n="_parent"&gt; tag.

I need to build TreeView with LINQ query, something like an example in the How to use Linq to Xml to get tree data with recursive querying? 

var dataSource = (from results in ids.Items.Descendants("nodeObject")
                                  select new nodeObject
                                  {
                                      nodeName = results.Element("nodeName").Value.ToString(),
                                      nodeChildren = this.GetChilden(results)
                                  });


Currently, my solution is 

            List&lt;I&gt; xi = (from c in ids.Items
                          where !(
                                    from b in c.T.ToList()
                                    select b.n
                                  ).Contains("_parent")
                          select c
                 ).ToList&lt;I&gt;();

            foreach (I iobj in xi)
            {
                String nameId = iobj.T.ToList()
                    .Where(zxc =&gt; zxc.n.Equals("_display_name"))
                    .First().Value;

                uint elNameUint = Convert.ToUInt32(nameId, 16);
                String elName = translations[elNameUint];

                TreeNode treeNode = new TreeNode(elName);
                treeNode.Tag = iobj.rie.Instance;

                treeView1.Nodes.Add(treeNode);
            }

            xi = (from c in ids.Items
                  where (
                            from b in c.T.ToList()
                            select b.n
                          ).Contains("_parent")
                  select c

                ).ToList&lt;I&gt;();

            while (xi.Count &gt; 0)
            {
                foreach (I iobj in xi)
                {
                    String nameId = iobj.T.ToList()
                        .Where(zxc =&gt; zxc.n.Equals("_display_name"))
                        .First().Value;

                    String parentId = iobj.T.ToList()
                       .Where(zxc =&gt; zxc.n.Equals("_parent"))
                       .First().Value;

                    uint elNameUint = Convert.ToUInt32(nameId, 16);
                    String elName = translations[elNameUint];


                    TreeNode treeNode = new TreeNode(elName);
                    treeNode.Tag = iobj.rie.Instance;

                    TreeNode ttmp = FindNode(treeView1.Nodes, parentId);
                    if (ttmp != null)
                    {
                        ttmp.Nodes.Add(treeNode);
                        xi.Remove(iobj);
                        break;
                    }
                }
            }

            treeView1.ExpandAll();


But I think, that my solution with breaks isn't a very  clean solution and I was hoping to figure out a more elegant solution using LINQ
Don't fetishise List&lt;&gt;


            List&lt;I&gt; xi = (from c in ids.Items
                          where !(
                                    from b in c.T.ToList()
                                    select b.n
                                  ).Contains("_parent")
                          select c
                 ).ToList&lt;I&gt;();



c.T is an array: what benefit is there to calling ToList() on it? There are two reasons for using ToList() on an enumerator: it's a lazy enumerator which you want to evaluate fully, or you need some specific method from List. Here neither of these applies.

It's not clear to me that xi needs to be eager either. I think that a first refactor could be to

            var xi = (from c in ids.Items
                          where !(
                                    from b in c.T
                                    select b.n
                                  ).Contains("_parent")
                          select c
                 );


Personally I'm not a fan of the SQL-like LINQ syntax. I'd find this more readable as

            var xi = ids.Items.Where(item =&gt; !item.T.Any(t =&gt; t.n == "_parent"));


There are various other instances of the same unnecessary or even counterproductive use of ToList().



Learn the LINQ overloads


                String nameId = iobj.T.ToList()
                    .Where(zxc =&gt; zxc.n.Equals("_display_name"))
                    .First().Value;



Instead of Where(...).First() you can just use First(...):

                String nameId = iobj.T.First(zxc =&gt; zxc.n.Equals("_display_name")).Value;




Don't do pointless work


            while (xi.Count &gt; 0)
            {
                foreach (I iobj in xi)
                {
                    String nameId = ...;

                    String parentId = ...;

                    // Do a lot of work with nameId
                    ...

                    TreeNode ttmp = FindNode(treeView1.Nodes, parentId);
                    if (ttmp != null)
                    {
                        ttmp.Nodes.Add(treeNode);
                        xi.Remove(iobj);
                        break;
                    }
                }
            }



A given I instance might not find its parent until the 100th time round the outer loop, which means that 99 times it will construct a node and then hand it off to the garbage collector without it ever being needed. That's not only bad for performance: it's confusing for the maintenance programmer. Compare this rewrite:

            while (xi.Count &gt; 0)
            {
                foreach (I iobj in xi)
                {
                    String parentId = ...;

                    TreeNode ttmp = FindNode(treeView1.Nodes, parentId);
                    if (ttmp != null)
                    {
                        String nameId = ...;

                        // Do a lot of work with nameId
                        ...

                        ttmp.Nodes.Add(treeNode);
                        xi.Remove(iobj);
                        break;
                    }
                }
            }




Avoid linear time insertions, deletions, and searches where possible

E.g.


                    String nameId = iobj.T.ToList()
                        .Where(zxc =&gt; zxc.n.Equals("_display_name"))
                        .First().Value;

                    String parentId = iobj.T.ToList()
                       .Where(zxc =&gt; zxc.n.Equals("_parent"))
                       .First().Value;



Even rewriting that to ditch to ToList() and use First(...), it's doing multiple linear searches through the same array. I would want to investigate whether I could refactor to replace IT[] T with IDictionary&lt;string, string&gt; T.

If I can't, I would strongly consider introducing a local struct or class to wrap iobj, nameId, and parentId so that the search can be done once.

Then in this main loop, xi has elements at random positions selected for removal. In that case it should under no means be a List&lt;&gt;. ISet is far more appropriate for random removals.

FindNode isn't supplied, but I suspect that it also does a linear search. There's nothing stopping you from introducing an IDictionary&lt;string, TreeNode&gt; to find the parents quickly.



Think in parallel

(Or: a lot of the preceding was because they're important lessons, but I'm now going to recommend throwing most of the code away and rewriting from scratch).

Why is it necessary to first find the roots and then build parents? And why is it necessary to break out of the inner loop in the second half when you've found a node whose parent is already in the tree? [NB That's a rhetorical question: I know that you're doing it to avoid a concurrent modification exception, but there are standard workarounds for that which are less inefficient].

In particular, is there any reason not to structure things like this?

IDictionary&lt;string, Tuple&lt;I, TreeNode&gt;&gt; nodes = ids.Items.ToDictionary(
    item =&gt; ...,
    item =&gt; ...);

foreach (var pair in nodes.Values)
{
    if (ItemHasParent(pair.Item1))
    {
        TreeNode parentNode = ...;
        parentNode.Nodes.Add(pair.Item2);
    }
    else
    {
        treeView1.Nodes.Add(pair.Item2);
    }
}