Dinuka Jayasuriya Dinuka Jayasuriya - 11 days ago 12x
C# Question

C# Manually Sorting Parent/Child tree elements in a list

I am attempting to generate a list of elements that would generate a tree structure if visualized.


Element 1 -> 1, 0 //ID is 1 & Parent ID is 0 (0 = root)
Element 2 -> 2, 0 //ID is 2 & Parent ID is 0 (0 = root)
Element 3 -> 3, 1 //ID is 3 & Parent ID is 1
Element 4 -> 4, 3
Element 5 -> 5, 2

If a tree is to be visualized with this structure:

enter image description here

To make this work, here's the Node Class:

public class Node
public string id;
public string parentId;
public List<Node> children = new List<Node>();

Similar to a tree, a node may contain a parent and it also may contain multiple other
children nodes

The task is to sort the elements to their proper hierarchy & add child elements to their respective parent's children collection. There are 2 methods in my mind:

1) The Loop Method

i) Loop & find the Base/root nodes (nodes with parent as 0)

ii) Loop & find the nodes with the base nodes as their parent

iii) Add them to the base node's children collection

However the above method is best applicable for a tree of depth 2, meaning the root & their immediate child levels. Imagine a tree with multiple complex levels. This method won't work for that.

That's what I've tried so far.

2) The 'Recursion' method

The second method would be the 'Recursion' method. That's what I can't seem to figure out yet. Can anyone help me with this problem?

Has anyone attempted to solve this problem before? How can I arrange a list containing 'n' number of elements with their Parent ID & ID defined?


If I understand correctly, you have a flat List<Node> and you want to populate children property and end up with a list of the root nodes.

This can be achieved efficiently by building a fast lookup structure by id (like Dictionary) and single iteration over the source list. For each node you'll find the parent node and add the node to the parent children list (or to root list if there is no parent). The time complexity of the algorithm will be O(N).

static List<Node> BuildTree(List<Node> nodes)
    var nodeMap = nodes.ToDictionary(node => node.id);
    var rootNodes = new List<Node>();
    foreach (var node in nodes)
        Node parent;
        if (nodeMap.TryGetValue(node.parentId, out parent))
    return rootNodes;