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<TreeNode>`, 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<Tree> 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<TreeNode> 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<Tree>();

        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        --->     |     |--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        --->        |  |--drivers
4     D:             0                    |     |--oem 
5     data           2                    | 
6     E:             0                    |--D:        
                                          |  |--data   
                                          |
                                          |--E:       

```