Remove Sub-Folders from the Filesystem

Medium · Tries · Explanation and code example

Trie

How it works

A trie naturally represents hierarchical folder structures. Each node corresponds to a folder name segment, and we mark nodes that represent complete folder paths. When checking if a folder is a subfolder, we traverse the trie along its path. If we encounter a marked node before reaching the end, a parent folder exists, meaning this is a subfolder.

Steps

  1. Build a trie by inserting all folder paths:
    • Split each path by / and traverse or create nodes for each segment.
    • Mark the final node as end_of_folder.
  2. For each folder, search the trie:
    • Traverse the path segment by segment using an index i from 0 to len(folders) - 1.
    • If any node before the last is marked as end_of_folder, skip this folder.
  3. Add non-subfolder paths to res.
  4. Return the res list.

Complexity

  • Time complexity: O(n * m)
  • Space complexity: O(n * m)

Where n is the size of the string array folder and m is the length of each string.

Things to watch for

Matching Partial Folder Names as Subfolders

A folder /a/bc is not a subfolder of /a/b, even though /a/b is a prefix of /a/bc. The subfolder relationship requires matching at a / boundary. Always append / when checking prefixes or compare path segments individually to avoid false positives.

Forgetting to Handle the Root Slash

Every path starts with /, which creates an empty string when splitting by /. Failing to skip or handle this empty segment causes index errors or incorrect trie traversal. Ensure your parsing logic accounts for the leading slash.

Incorrect Sorting Assumptions

When using the sorting approach, you must compare against the last added result folder, not any arbitrary previous folder. Since sorted order ensures parents come before children, only the most recent result can be the parent of the current folder. Comparing against all previous results is both unnecessary and error-prone.

Python code example

from typing import List

class Trie:
    def __init__(self):
        self.children = {}  # string -> Trie
        self.end_of_folder = False

    def add(self, path: str) -> None:
        cur = self
        for f in path.split("/"):
            if f not in cur.children:
                cur.children[f] = Trie()
            cur = cur.children[f]
        cur.end_of_folder = True

    def prefix_search(self, path: str) -> bool:
        cur = self
        folders = path.split("/")
        for i in range(len(folders) - 1):
            cur = cur.children[folders[i]]
            if cur.end_of_folder:
                return True
        return False


class Solution:
    def removeSubfolders(self, folder: List[str]) -> List[str]:
        trie = Trie()
        for f in folder:
            trie.add(f)

        res = []
        for f in folder:
            if not trie.prefix_search(f):
                res.append(f)
        return res

C++ code example

class Trie {
public:
    Trie* children[128] = {};
    bool end_of_folder = false;

    void add(const string& path) {
        Trie* cur = this;
        string part;
        for (int i = 0; i < path.size(); i++) {
            if (path[i] == '/') {
                if (!part.empty()) {
                    for (char c : part) {
                        if (!cur->children[(int)c]) cur->children[(int)c] = new Trie();
                        cur = cur->children[(int)c];
                    }
                    if (!cur->children[(int)'/']) cur->children[(int)'/'] = new Trie();
                    cur = cur->children[(int)'/'];
                    part.clear();
                }
            } else {
                part += path[i];
            }
        }
        if (!part.empty()) {
            for (char c : part) {
                if (!cur->children[(int)c]) cur->children[(int)c] = new Trie();
                cur = cur->children[(int)c];
            }
            if (!cur->children[(int)'/']) cur->children[(int)'/'] = new Trie();
            cur = cur->children[(int)'/'];
        }
        cur->end_of_folder = true;
    }

    bool prefixSearch(const string& path) {
        Trie* cur = this;
        string part;
        for (int i = 0; i < (int)path.size(); i++) {
            if (path[i] == '/') {
                if (!part.empty()) {
                    for (char c : part) cur = cur->children[(int)c];
                    cur = cur->children[(int)'/'];
                    if (cur->end_of_folder) return true;
                    part.clear();
                }
            } else {
                part += path[i];
            }
        }
        return false;
    }
};

class Solution {
public:
    vector<string> removeSubfolders(vector<string>& folder) {
        Trie trie;
        for (auto& f : folder) trie.add(f);
        vector<string> res;
        for (auto& f : folder) {
            if (!trie.prefixSearch(f)) res.push_back(f);
        }
        return res;
    }
};
Source and license

Adapted from NeetCode’s source · MIT license. Node types are supplied by LeetCode where needed.

Check the explanation on LeetCode

Your recall check is in progress. Write your attempt before revealing the explanation.

Resume recall check

Browse all problem explanations