Building a Tree from a flat List This is my incoming data:

id      text    parent
--      ----    ------
0       0       NULL
1       1       0
11      11      1
2       2       0
21      21      2
211     211     21
22      22      2
3       3       0


Which I receive in a List&lt;TreeNode&gt;, where TreeNode is:

public class TreeNode
{
    public int id { get; set; }
    public string text { get; set; }
    public int? parent { get; set; }
}


To represent my tree,

0
|--1
|  |--11
|
|--2
|  |--21
|  |  |--211
|  |
|  |--22
|
|--3


I have this class:

public class Tree
{
    public int? id { get; set; }
    public string text { get; set; }
    public List&lt;Tree&gt; children { get; set; }
}


I build the tree from the flat list of nodes with this:

Tree tree = treeNodes.BuildTree();


This is my implementation of BuildTree:

public static Tree BuildTree(this List&lt;TreeNode&gt; nodes)
{
    // Create a NULL-root tree
    Tree root = new Tree();

    // Add nodes (sub-trees) to the tree
    foreach (TreeNode node in nodes)
    {
        // traverse tree, find the parent, add child
        root.TraverseAndAddNode(node);
    }

    // Return the NULL-root
    // If the tree has an actual root, it will be the first child of this root
    return root;
}

public static bool TraverseAndAddNode(this Tree root, TreeNode node)
{
    bool nodeAdded = false;

    // Check if the current root is the parent of the node to be added
    if (root.id == node.parent)
    {
        if (root.children == null)
            root.children = new List&lt;Tree&gt;();

        root.children.Add(new Tree()
        {
            id = node.id,
            text = node.text,
            children = null
        });

        nodeAdded = true;
    }
    // Check if the current root has children and recurse the search
    else if (root.children != null)
    {
        foreach (Tree tree in root.children)
        {
            nodeAdded = tree.TraverseAndAddNode(node);

            if (nodeAdded)
                break;
        }
    }
    // Node's parent is not in the current tree
    else
    {
        nodeAdded = false;
    }

    return nodeAdded;
}


I'm able to see a few problems here, such as the traversal code here is not efficient as it uses linear search, and the implementation would be better off done with a Dictionary, and also that I'm unnecessarily creating a NULL root for the lack of being able to dynamically identify the true root from the flat data.

How can I do better? Is there a way I can dynamically construct partial sub-trees as I parse the flat-data, and keep linking these partially constructed trees to the main tree and keep building on?

EDIT:
* Removed nullable id from TreeNode -- changed int? id to int id
* Updated incorrect original example showing 1.1 instead of 11 

Added the following examples:

Case 1:
Multiple NULL parents (NULL root is acceptable):

id    text           parent            NULL 
--    ----           ------            | 
1     C:             NULL              |--C:        
2     drivers        1                 |  |--drivers 
3     oem            2        ---&gt;     |     |--oem  
4     D:             NULL              | 
5     data           2                 |--D:        
6     E:             NULL              |  |--data    
                                       |
                                       |--E:       


Case 2:
Single NULL parent (NULL root is avoidable):

id    text           parent            NULL
--    ----           ------            |
0     My PC          NULL              |--My PC
1     C:             0                    | 
2     drivers        1                    |--C:        
3     oem            2        ---&gt;        |  |--drivers
4     D:             0                    |     |--oem 
5     data           2                    | 
6     E:             0                    |--D:        
                                          |  |--data   
                                          |
                                          |--E:
Well your provided example data can't be real, because I never ever saw an int? which could take 1.1 as value.  

I will apply to the posted code the standard C# naming convention, meaning that properties are named using PascalCase casing.  

That being said, lets take a look at the Tree class 


public class Tree
{
    public int? id { get; set; }
    public string text { get; set; }
    public List&lt;Tree&gt; children { get; set; }
}  



which seems to be just a TreeNode with children and without a parent. IMO this is too much. Just add your TreeNode to a List&lt;TreeNode&gt; Children property and you won't need the Tree class anymore.  


By initializing the Children property at creation of the object, you will waste some space (memory) but you won't need to check if Children == null anymore.  
If the root node (parent == null) won't be the first node in the collection then your method will fail.
Omitting braces although they might be optional is dangerous because this can lead to hidden and therefore hard to find bugs.

I would like to encourage you to always use them.  
Using recursion to tackle this problem is a good idea.  


Another approach

which assumes the TreeNode looks like so  

public class TreeNode
{
    public int? Id { get; set; }
    public string Text { get; set; }
    public int? Parent { get; set; }
    public List&lt;TreeNode&gt; Children { get; set; }

    public TreeNode()
    {
        Children = new List&lt;TreeNode&gt;();
    }
}  


where I would usually make the setters private and fill the properties at constructor level, but I will leave this for you to do.


By using FirstOrDefault() we can get the root node very easily and should remove it from the nodes collection. Let us introduce a method to do this  

private static TreeNode RemoveRootNode(this List&lt;TreeNode&gt; nodes)
{
    if (nodes == null)
    {
        throw new NullReferenceException("nodes");
    }

    var root = nodes.FirstOrDefault(n =&gt; !n.Parent.HasValue);
    if (root != null)
    {
        nodes.Remove(root);
    }

    return root;
}  


Now we don't need the root node to be the first item in the collection anymore.  

Next we need the "main"  method which takes a List&lt;TreeNode&gt; as a parameter and returns a TreeNode which is the root node like so  

public static TreeNode BuildTree(this List&lt;TreeNode&gt; nodes)
{
    var root = nodes.RemoveRootNode();
    if (root == null) { throw new ArgumentOutOfRangeException("nodes"); }
    return root.BuildTree(nodes);
}  




Edit

Based on the changed example data, we now can have multiple TreeNode with Parent == null which makes the RemoveRootNode() method superfluous and will result in TreeNode buildTree(this List&lt;TreeNode&gt;) like so  

public static TreeNode BuildTree(this List&lt;TreeNode&gt; nodes)
{
    if (nodes == null)
    {
        throw new ArgumentNullException("nodes");
    }
    return new TreeNode().BuildTree(nodes);
}


As we see there should be a BuildTree(this TreeNode, List&lt;TreeNode&gt;) method which will look like: 

private static TreeNode BuildTree(this TreeNode root, List&lt;TreeNode&gt; nodes)
{
    if (nodes.Count == 0) { return root; }

    var children = root.FetchChildren(nodes).ToList();
    root.Children.AddRange(children);
    root.RemoveChildren(nodes);

    for (int i = 0; i &lt; children.Count; i++)
    {
        children[i] = children[i].BuildTree(nodes);
        if (nodes.Count == 0) { break; }
    }

    return root;
} 


which is self-explanatory. It fetches the children by using  

public static IEnumerable&lt;TreeNode&gt; FetchChildren(this TreeNode root, List&lt;TreeNode&gt; nodes)
{
    return nodes.Where(n =&gt; n.Parent == root.Id);
}  


and add them to the Children property of the root node and removes them from the nodes by  

public static void RemoveChildren(this TreeNode root, List&lt;TreeNode&gt; nodes)
{
    foreach (var node in root.Children)
    {
        nodes.Remove(node);
    }
}


Then it iterates over the the children and calls itself recursively.