Introduction

Generating a hierarchy usually means turning a flat list of items with Id and ParentId fields into a tree. In .NET applications this comes up in menus, category trees, organization charts, and comment threads. The best algorithm is usually not recursive searching over the whole list, but a two-phase pass that builds lookup structures first and then links parents to children in O(n) time.

Start From a Flat Model

Suppose each record looks like this:

• 'Id: unique identifier'
• 'ParentId: nullable identifier of the parent'
• 'Name: display label'

A simple C# model is enough:

1using System;
2using System.Collections.Generic;
3
4public sealed class Node
5{
6    public int Id { get; init; }
7    public int? ParentId { get; init; }
8    public string Name { get; init; } = "";
9    public List<Node> Children { get; } = new();
10}

The goal is to transform a flat List<Node> into a set of roots whose Children collections contain the full hierarchy.

Use a Lookup, Not Repeated Scans

A common slow approach is: for each node, scan the whole list to find its children. That costs O(n^2) and becomes painful on large inputs.

A better approach is:

1. build a dictionary from Id to node
2. loop once through the nodes
3. if ParentId exists, append the node to its parent’s Children
4. otherwise, treat it as a root

That turns the linking phase into near-constant-time dictionary lookups per node.

1using System;
2using System.Collections.Generic;
3using System.Linq;
4
5public static class HierarchyBuilder
6{
7    public static List<Node> BuildTree(IEnumerable<Node> flatNodes)
8    {
9        var all = flatNodes.ToDictionary(n => n.Id);
10        var roots = new List<Node>();
11
12        foreach (var node in all.Values)
13        {
14            if (node.ParentId is null)
15            {
16                roots.Add(node);
17                continue;
18            }
19
20            if (!all.TryGetValue(node.ParentId.Value, out var parent))
21            {
22                throw new InvalidOperationException(
23                    $"Missing parent {node.ParentId.Value} for node {node.Id}");
24            }
25
26            parent.Children.Add(node);
27        }
28
29        return roots;
30    }
31}

This is usually the right baseline algorithm because it is clear, fast, and easy to test.

Displaying the Result

Once the tree exists, traversal is straightforward.

1public static void PrintTree(IEnumerable<Node> nodes, int depth = 0)
2{
3    foreach (var node in nodes)
4    {
5        Console.WriteLine($"{new string(' ', depth * 2)}- {node.Name}");
6        PrintTree(node.Children, depth + 1);
7    }
8}

And a runnable example:

1var items = new List<Node>
2{
3    new() { Id = 1, ParentId = null, Name = "Company" },
4    new() { Id = 2, ParentId = 1, Name = "Engineering" },
5    new() { Id = 3, ParentId = 1, Name = "Finance" },
6    new() { Id = 4, ParentId = 2, Name = "Platform" },
7};
8
9var roots = HierarchyBuilder.BuildTree(items);
10PrintTree(roots);

Handle Invalid Data Explicitly

Real data often contains problems:

• a node points to a missing parent
• the same id appears twice
• a cycle exists, such as A being a descendant of itself

The dictionary approach already catches duplicate ids because ToDictionary fails. Missing parents should also fail fast unless your application explicitly wants to keep such nodes as extra roots.

Cycle detection is a separate concern. If your input might be corrupted, add a traversal step that tracks visited ids along the current path. That is worth doing when data comes from users or external imports.

When Ordering Matters

Tree construction and child ordering are separate decisions. If the UI expects alphabetical or numeric order, sort either before linking or after building each Children list.

Do not mix sorting logic into the core hierarchy algorithm unless ordering is part of the domain model. Keeping those concerns separate makes the code easier to maintain.

Common Pitfalls

• Building the hierarchy by repeatedly scanning the full list, which leads to O(n^2) behavior.
• Recursing before building a lookup and making child lookup unnecessarily expensive.
• Ignoring invalid input such as missing parents or duplicate ids.
• Forgetting that a hierarchy may have multiple roots, not just one.
• Assuming the input is acyclic when imported data can contain loops.

Summary

• The usual input is a flat list with Id and ParentId.
• The practical algorithm is to build an Id lookup and link children in one pass.
• That approach runs in roughly O(n) time for tree construction.
• Validate duplicates, missing parents, and possible cycles explicitly.
• Treat sorting and rendering as separate concerns from hierarchy generation.