How to convert a series of parent-child relationships into a hierarchical tree?

To convert a flat list of parent-child rows into a tree, build a map from each id to a new node in one pass, then loop over the rows again and append each node to its parent's children list. A row whose parent is null is a root. The whole conversion is O(n) time and O(n) space for n rows. The input order does not matter, because every node exists in the map before any parent lookup happens. This is the standard answer to "array to tree", "build an org chart from an employees table", and "nest categories by parent id".

The Input Shape

The input is one row per node, each carrying its own id and its parent's id. This is how the data arrives from a SQL table with a self-referencing foreign key, from a CSV export, or from an API. The example below is a small company.

The output is a nested structure. The CEO node holds a list with the CTO and CFO nodes, the CTO node holds the Dev Manager, and so on.

The Algorithm

1. Create an empty map from id to node.
2. For every row, create a node with the row's fields and an empty children list, and store it in the map under its id.
3. For every row again, look up its node. If parent_id is null, add the node to the roots list. Otherwise look up the parent in the map and append the node to the parent's children.
4. Return the roots list. For a proper tree it holds one node.

Step 2 is the single pass that builds the map. Step 3 needs the map to be complete, which is why it is a separate loop rather than part of step 2. If the two loops were merged, a child that appears before its parent in the input would fail its lookup.

Python Solution

def build_tree(rows):
    nodes = {}
    for row in rows:
        nodes[row["id"]] = {"id": row["id"], "name": row["name"], "children": []}

    roots = []
    for row in rows:
        node = nodes[row["id"]]
        parent_id = row["parent_id"]
        if parent_id is None:
            roots.append(node)
        elif parent_id in nodes:
            nodes[parent_id]["children"].append(node)
        else:
            raise ValueError(f"row {row['id']} points to missing parent {parent_id}")
    return roots


rows = [
    {"id": 1, "name": "CEO", "parent_id": None},
    {"id": 2, "name": "CTO", "parent_id": 1},
    {"id": 3, "name": "CFO", "parent_id": 1},
    {"id": 4, "name": "Dev Manager", "parent_id": 2},
    {"id": 5, "name": "Developer", "parent_id": 4},
    {"id": 6, "name": "Accountant", "parent_id": 3},
]
tree = build_tree(rows)
print(tree[0]["name"], [c["name"] for c in tree[0]["children"]])
# CEO ['CTO', 'CFO']

Trace the root by hand. Row 1 has a parent_id of None, so the first branch runs and the CEO node goes into roots. Row 2 has a parent_id of 1, and nodes[1] exists because the first loop finished, so the CTO node is appended to the CEO's children. Every other row follows the second branch in the same way.

JavaScript Solution

function buildTree(rows) {
  const nodes = new Map();
  for (const row of rows) {
    nodes.set(row.id, { id: row.id, name: row.name, children: [] });
  }

  const roots = [];
  for (const row of rows) {
    const node = nodes.get(row.id);
    if (row.parentId == null) {
      roots.push(node);
    } else if (nodes.has(row.parentId)) {
      nodes.get(row.parentId).children.push(node);
    } else {
      throw new Error(`row ${row.id} points to missing parent ${row.parentId}`);
    }
  }
  return roots;
}

const rows = [
  { id: 1, name: "CEO", parentId: null },
  { id: 2, name: "CTO", parentId: 1 },
  { id: 3, name: "CFO", parentId: 1 },
  { id: 4, name: "Dev Manager", parentId: 2 },
  { id: 5, name: "Developer", parentId: 4 },
  { id: 6, name: "Accountant", parentId: 3 },
];
const tree = buildTree(rows);
console.log(tree[0].name, tree[0].children.map((c) => c.name));
// CEO [ 'CTO', 'CFO' ]

The comparison row.parentId == null is deliberate. It is true for both null and undefined, so a row that omits the field is treated as a root. A Map is used rather than a plain object so that numeric and string ids are not merged.

Complexity and Edge Cases

Time is O(n) and space is O(n). Each loop touches every row once, and each map lookup is O(1) on average. The map holds one entry per row, and the tree reuses those same node objects, so no copies are made.

Several roots. A forest, which is a set of trees, appears when more than one row has a null parent. The function returns all of them, so a caller who expects a single tree should check len(roots).

Missing parent. A row that names a parent id not present in the input is an error in the data. The code above raises. An alternative is to treat that row as a root, which hides the problem and is usually the wrong choice.

Cycles. If row A names B as its parent and B names A, neither row is a root and each is attached to the other. The loop still finishes, because it never follows the links, but the result is not a tree. Detect it by counting: if the number of nodes reachable from the roots is smaller than n, a cycle exists.

Counting descendants. Once the tree exists, the number of descendants of a node is the sum, over its children, of one plus each child's descendant count. That is a short recursive function, and it is the follow-up question most often asked after the build.