# Roots and Branches

> Flat strings carry a hierarchy. Recover it.

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

Domain: Python · Difficulty: medium · Seniority: L5

## Problem

A storage indexer hands you object keys as slash-separated `paths`, and you need them folded into a nested dict that mirrors the directory layout: every directory segment maps to an inner dict and every file (the final segment) maps to `None`. Paths that share a leading directory must collapse onto the same node instead of clobbering each other, and an empty list yields an empty dict.

## Worked solution and explanation

### What this really is

Under the file-system costume this is a trie insert: you thread each path into a shared prefix structure one segment at a time. Anyone can split on the slash and nest dicts. The thing that separates candidates is prefix sharing: when the second path under `src/` shows up, do you reuse the `src` node you already created, or do you replace it with a fresh `{}` and silently lose the first file? Get that wrong and `src/main.py` vanishes the moment `src/utils/helper.py` is inserted.

> **Trick to solving**
>
> `dict.setdefault(key, {})` returns the existing child if the key is present and inserts-then-returns a fresh dict if it is not. That single call replaces the whole 'if key not in current: create it' dance and makes the overwrite bug structurally impossible to write.

---

### Walking it

#### Step 1: Separate the directories from the file

`'src/utils/helper.py'.split('/')` gives `['src', 'utils', 'helper.py']`. Peel the last element off as the filename and treat everything before it as the directory chain: `*directories, filename = parts`.

#### Step 2: Descend, reusing existing nodes

Start at the root dict and descend one directory at a time, calling `setdefault` at each level. The key move is that descent always lands on the node that is already there when one exists, so files inserted by earlier paths stay put.

#### Step 3: Mark the leaf file as None

Once you are standing on the deepest directory node, write the filename with a value of `None`. That `None` is what distinguishes a file from an (empty) directory dict downstream.

---

### The solution

**Iterative trie insert with setdefault**

```python
def build_file_tree(paths: list[str]) -> dict:
    tree = {}
    for path in paths:
        *directories, filename = path.split('/')
        node = tree
        for directory in directories:
            node = node.setdefault(directory, {})
        node[filename] = None
    return tree
```

**Manual existence check**

for directory in directories:
    if directory not in node:
        node[directory] = {}
    node = node[directory]

Correct, but the create-then-descend is two statements and one stray reassignment turns it into the overwrite bug.

**setdefault**

for directory in directories:
    node = node.setdefault(directory, {})

Same compute, one line, and reuse-or-create is atomic so the bug cannot sneak in.

> **Common pitfall**
>
> Recreating a directory node on a later path. Paths `src/a.py` and `src/b.py` must share the one `src` dict; if the second insert assigns `node['src'] = {}` unconditionally, `a.py` is gone. In a real file system a name cannot be both a fresh empty directory and the home of an existing file.

> **Interviewers watch for**
>
> Whether you reach for `setdefault` (or `defaultdict`) unprompted. Candidates who write the manual if-not-in check still pass, but the ones who reuse the node idiomatically signal they have built nested structures before.

> **Performance insight**
>
> Time is O(total segments across all paths): each segment is visited once. Space is O(total segments) for the tree. There is no way to beat a single pass, since every segment must be placed.

---

## Common follow-up questions

- How would you flatten the tree back into the original list of paths? _(Tests recursive DFS with path accumulation.)_
- What if you need to count files per directory, including subdirectories? _(Tests post-order traversal counting leaves.)_
- How would you handle paths with trailing or leading slashes? _(Tests stripping empty segments from the split result.)_
- What if two paths conflict, where one name is a file and another path treats it as a directory? _(Tests validation and conflict resolution.)_

## Related

- [All practice problems](https://datadriven.io/problems)
- [Mock interview mode](https://datadriven.io/interview/roots_and_branches)
- [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). DataDriven is the data engineering interview community. Live code execution in SQL, Python, and Spark sandboxes. Every feature is open to every member.