C++ | Short step by step easy to understand | Build a Trie
Note: I could not solve this completely during contest. Try to grasp it one step at a time.\n\nAlgorithm\n1. We will be building a trie. Every node of the trie 
**Note**: I could not solve this completely during contest. Try to grasp it one step at a time.\n\n**Algorithm**\n1. We will be building a trie. Every node of the trie will store :\n\t```\n\tend -> Is the path ending here\n\texclude -> should this be excluded/pruned while constructing the final answer\n\tname -> name of the directory\n\tchild -> the children we have for this node\n\t```\n1. Using ```paths``` contruct the Trie with help of ```insert``` function.\n2. Perform ```dfs``` on Trie and obtain ```childPath``` which is a serialization of the subtree rooted at current node excluding current node.\n3. Record the current node as parent of ```childPath``` in ```parentMap```.\n4. For every key in  ```parentMap```, mark ```exclude = true``` for all nodes if size of value (vector of parents) > 1 (Their subtrees have occured more than once and hence need to be excluded).\n5. Use ```getans``` to build our answer. (Here we check if ```root->end = true```)\n\n**Note:** We use ```map<string, node*> child``` instead of ```unordered_map<string, node*> child``` to guarantee correct serialization. Thanks @chenjun15\n\n**Code**\n```\nclass node{\n    public: \n        map<string, node*> child;\n        bool end;\n        bool exclude;\n        string name;\n        node(string fname){\n            exclude = false;\n            end = false;\n            name = fname;\n        }\n};\n\nclass Solution {\npublic:\n    node *root;\n    unordered_map<string, vector<node*>> parentMap;\n    vector<vector<string>> ans;\n    vector<vector<string>> deleteDuplicateFolder(vector<vector<string>>& paths) {\n        root = new node("/");\n        for(int i = 0 ; i < paths.size(); i++) insert(root, paths[i], 0);\n        dfs(root);\n        for(auto &e : parentMap)\n            if(e.second.size() > 1)\n                for(auto &parent : e.second)\n                    parent->exclude = true;\n        vector<string> temp;\n        getans(root, temp);\n        return ans;\n    }\n    \n    void getans(node *root, vector<string> &temp){\n        if(root->exclude) return;\n        if(root->name != "/") temp.push_back(root->name);\n        if(root->end) ans.push_back(temp);\n        for(auto &e : root->child)\n            getans(e.second, temp);\n        if(root->name != "/") temp.pop_back();\n    }\n    \n    string dfs(node *root){\n        string childPath = "";\n        for(auto &e : root->child){\n            childPath += dfs(e.second);\n            childPath += "|";\n        }\n        if(childPath != "") parentMap[childPath].push_back(root);\n        return root->name + "|" + childPath;\n    }\n    \n    void insert(node *root, vector<string> &path, int pos){\n        if(pos < path.size()){\n            if(root->child.count(path[pos]) == 0) root->child[path[pos]] = new node(path[pos]);\n            insert(root->child[path[pos]], path, pos+1);\n        }\n        else if(pos == path.size()) root->end = true;\n    }\n};\n```
['Trie', 'C']