Introduction

Turning a flat table into a tree is a standard parent-child reconstruction problem. The most efficient general approach is usually to create every node once, index those nodes by identifier, and then attach each node to its parent in a second linear pass.

Model the Flat Table Explicitly

Assume each row has its own id and an optional parent_id. A root row has no parent. For example:

1rows = [
2    {"id": 1, "name": "CEO", "parent_id": None},
3    {"id": 2, "name": "CTO", "parent_id": 1},
4    {"id": 3, "name": "CFO", "parent_id": 1},
5    {"id": 4, "name": "Engineer", "parent_id": 2},
6    {"id": 5, "name": "Accountant", "parent_id": 3},
7]

This input is flat because every row is just a record. The hierarchy only exists implicitly through the parent_id references.

The Efficient One-Pass Attachment Pattern

The key optimization is to avoid scanning the whole table every time you want to find children. A recursive solution that repeatedly searches for children can degrade to quadratic time. Instead, create a lookup dictionary first.

1from pprint import pprint
2
3
4def build_tree(rows):
5    nodes = {
6        row["id"]: {
7            "id": row["id"],
8            "name": row["name"],
9            "children": []
10        }
11        for row in rows
12    }
13
14    roots = []
15
16    for row in rows:
17        node = nodes[row["id"]]
18        parent_id = row["parent_id"]
19
20        if parent_id is None:
21            roots.append(node)
22        else:
23            parent = nodes[parent_id]
24            parent["children"].append(node)
25
26    return roots
27
28
29tree = build_tree(rows)
30pprint(tree)

This approach is typically O(n) time and O(n) space. Every row is processed a constant number of times, and parent lookup is fast because it uses a hash map.

Why Recursive Child Search Is Slower

A common first solution is recursive: start at the root, scan the whole list for children, recurse into each child, and repeat. That is easy to write, but if every recursive step scans the entire input again, performance gets worse as the dataset grows.

For small tables, that may be fine. For larger tables such as categories, comments, menus, or organizational data, it becomes wasteful quickly. The indexed-node approach scales better because parent lookup is direct.

Validate the Input Before Trusting the Tree

Real-world data is not always clean. A few checks are worth adding:

• a row should not reference a missing parent
• a row should not reference itself as its parent
• the graph should not contain cycles
• root-count rules should match your domain

Here is a simple missing-parent guard:

1def build_tree_safe(rows):
2    nodes = {
3        row["id"]: {
4            "id": row["id"],
5            "name": row["name"],
6            "children": []
7        }
8        for row in rows
9    }
10
11    roots = []
12
13    for row in rows:
14        node = nodes[row["id"]]
15        parent_id = row["parent_id"]
16
17        if parent_id is None:
18            roots.append(node)
19            continue
20
21        if parent_id not in nodes:
22            raise ValueError(f"missing parent_id: {parent_id}")
23
24        nodes[parent_id]["children"].append(node)
25
26    return roots

Cycle detection is a separate concern from tree construction. If your data source can be corrupt, add a visited-state traversal before trusting the final structure.

Ordering Children Predictably

The basic algorithm preserves the input order in which children are attached. If you need sorted children, sort after the structure is built.

1
2def sort_tree(nodes):
3    for node in nodes:
4        node["children"].sort(key=lambda child: child["name"])
5        sort_tree(node["children"])

Keeping construction and sorting separate often makes the code clearer.

Common Pitfalls

Scanning the full table repeatedly during recursion is the usual performance mistake. Build an index first.

Assuming the data is always a valid tree is risky. Missing parents and cycles should be considered explicitly.

Mixing tree construction with presentation rules such as sorting can make the logic harder to debug. Build first, then order if needed.

Summary

• The efficient general solution is to index nodes by id and attach children by parent_id.
• This approach is usually linear in time and space.
• Avoid repeated full-table scans during recursive child lookup.
• Validate missing-parent and cycle conditions if the input may be dirty.