C++ | Trie accepted solution
One thing that had me stuck was understanding that the whole subtree of a node needs to be compared. This is actually easier than trying to separate the individ
One thing that had me stuck was understanding that the whole subtree of a node needs to be compared. This is actually easier than trying to separate the individual paths. \n\nThere is also no reason to do the pruning in two steps as all the data is available when you add a second/third/forth parent node to the same subdirectory structure.\n\nIn anycase hope this helps someone.\n\nAll the best!!\n\n\n\n```\nclass Solution {\n    struct Node {\n        map<string,Node*> child;\n        bool duplicate=false;\n    };\n        \n    void build(Node* root,vector<vector<string>>& paths) {\n        for (auto& dirs : paths) {\n            Node* node=root;\n            for (auto& dir : dirs) {\n                if (node->child.count(dir) == 0) \n                    node->child[dir] = new Node;\n                node = node->child[dir];\n            }\n        }\n    }\n    \n    string prune(Node* node,unordered_map<string,vector<Node*>>& subdirs) {\n        if (node->child.size() == 0) \n            return "";\n        \n        string subdir("(");\n        for (auto& [dir,child] : node->child) \n            subdir += dir + prune(child,subdirs);        \n        subdir += ")";\n        \n        auto& nodes = subdirs[subdir];\n        nodes.push_back(node);\n        \n        if (nodes.size() > 1) {\n            nodes.front()->duplicate = true;\n            nodes.back()->duplicate = true;\n        }\n        return subdir;\n    }\n\n    void gather(Node *node,vector<string>& path,vector<vector<string>>& result) {\n        if (node->duplicate == false) {\n            if (path.size())\n                result.push_back(path);\n            for (auto& [dir, child] : node->child) {\n                path.push_back(dir);\n                gather(child,path,result);\n                path.pop_back();\n            }\n        }\n    }\n    \npublic:\n    vector<vector<string>> deleteDuplicateFolder(vector<vector<string>>& paths) {\n        Node root;\n        build(&root,paths); \n        \n        unordered_map<string,vector<Node*>> subdirs;\n        prune(&root,subdirs);\n        \n        vector<vector<string>> result;\n        vector<string> path;        \n        gather(&root,path,result);\n        \n        return result;\n    }\n};\n````
['Depth-First Search', 'Trie', 'C']