# The Hierarchy Builder

> Parent-child pairs, flat. Build the family tree.

Canonical URL: <https://datadriven.io/problems/the_hierarchy_builder>

Domain: Python · Difficulty: hard · Seniority: L5

## Problem

Given a list of [parent, child] pairs, build a nested dict tree. The root is the parent that never appears as a child. Each parent maps to a dict of its children (by name). Leaves have empty dicts {}. Assume a single root.

## Worked solution and explanation

### Why this problem exists in real interviews

This tests **tree construction from flat parent-child relationships**, a pattern used in org chart builders, category hierarchies, and file system reconstruction. It probes graph-to-tree conversion and root detection.

---

### Break down the requirements

#### Step 1: Build a children lookup

Map each parent to its list of children using a dict.

#### Step 2: Find the root node

The root is the node that appears as a parent but never as a child.

#### Step 3: Recursively build the nested dict

For each node, create a dict entry mapping it to the nested result of its children. Leaf nodes map to empty dicts.

---

### The solution

**Recursive tree construction from flat pairs**

```python
def build_tree(pairs: list) -> dict:
    children = {}
    all_children = set()
    all_parents = set()
    for parent, child in pairs:
        if parent not in children:
            children[parent] = []
        children[parent].append(child)
        all_children.add(child)
        all_parents.add(parent)
    root = None
    for p in all_parents:
        if p not in all_children:
            root = p
            break
    def build(node):
        subtree = {}
        if node in children:
            for child in children[node]:
                subtree[child] = build(child)
        return subtree
    result = {root: build(root)}
    return result
```

> **Time and Space Complexity**
>
> **Time:** O(n) where n is the number of pairs. Each pair is processed once.
> 
> **Space:** O(n) for the children lookup and nested output.

> **Interviewers Watch For**
>
> Whether you correctly identify the root node. The root is never a child in any pair. Hardcoding or guessing the root is a red flag.

> **Common Pitfall**
>
> Assuming pairs arrive in top-down order. The pairs can be in any order, so you must build the full children lookup before constructing the tree.

---

## Common follow-up questions

- What if there are multiple roots? _(Tests returning a list of trees or a forest structure.)_
- How would you flatten the tree back to pairs? _(Tests DFS traversal emitting (parent, child) at each edge.)_
- What if the data contains cycles? _(Tests cycle detection during tree construction using a visited set.)_
- How would you compute the depth of each node? _(Tests BFS level tracking or recursive depth parameter.)_

## Related

- [All practice problems](https://datadriven.io/problems)
- [Mock interview mode](https://datadriven.io/interview/the_hierarchy_builder)
- [Python Interview Questions](https://datadriven.io/python-interview-questions)
- [Data Engineering Interview Prep Guide](https://datadriven.io/data-engineer-interview-prep)
- [Daily Challenge](https://datadriven.io/daily)

---

Source: DataDriven (https://datadriven.io). 100% free data engineering interview prep. Live code execution against Postgres 16, Python 3.11, and Spark sandboxes. No paywall, no premium tier, no signup gate.