DFS | TRIE with TriePool | Marking nodes
First we create the Trie using the given path array.\nSince the constraints mention that If a node at any level is inserted, then it is made sure that all the o
First we create the Trie using the given path array.\nSince the constraints mention that If a node at any level is inserted, then it is made sure that all the other nodes before this node will be also be inserted.\n\nOnce the Trie is created, we do the dfs on the trie and try to serialize the subtrees each node. We map the subtree string to the parent node. While traversing if we find any node/string, which has already been visited then we mark the current node as deleted and the node which is present in the map also deleted.\n\nWe again do the dfs on the Trie tree in post order traversal fashion. And if any of the node is deleted then we don\'t visit the nodes under the current node.\n```\nclass Node {\npublic:\n    map<string, Node*> child;\n    bool isDeleted;\n    string name;\n};\nconst int nax = 1e6 + 100;\nNode pool[nax], *root;\nint nodeCnt = 0;\nmap<string, Node*> seen;\nvector< vector<string> > result;\n//factory method to get the Trie node\nNode *getNode(string data) {\n    Node *cur = &pool[++nodeCnt];\n    cur->isDeleted = false;\n    cur->child.clear();\n    cur->name = data;\n    return cur;\n}\n\n//Trie Like insert Tree Function\nvoid insert(Node *root, vector<string> &path) {\n    Node *cur = root;\n    for (auto x: path) {\n        if (cur->child[x] == nullptr) {\n            cur->child[x] = getNode(x);\n        }\n        cur = cur->child[x];\n    }\n}\n\n//update/mark the nodes to be deleted\nstring mark(Node *root) {\n    string subtree = "";\n    for (auto [chilldName, childPtr]: root->child) {\n        if (childPtr)\n            subtree += mark(childPtr);\n    }\n    //current node is leaf node\n    if (subtree.size() == 0) {\n        return "(" + root->name + ")";\n    }\n    //This subtree is present in some other part of the tree\n    if (seen.find(subtree) != seen.end()) {\n        seen[subtree]->isDeleted = root->isDeleted = true;\n    }\n    seen[subtree] = root;\n    return "(" + root->name + subtree + ")";\n}\n\nvoid dfs(Node *root, vector<string> path) {\n    if (root == nullptr || root->isDeleted) {\n        return ;\n    }\n    if (path.size() > 0) {\n        result.push_back(path);\n    }\n    for (auto [childName, childPtr]: root->child) {\n        path.push_back(childName);\n        dfs(childPtr, path);\n        path.pop_back();\n    }\n}\n\nclass Solution {\npublic:\n    vector<vector<string>> deleteDuplicateFolder(vector<vector<string>>& paths) {\n        nodeCnt = 0;\n        seen.clear();\n        result.clear();\n        //build Trie Like tree\n        root = getNode("");\n        for (auto path: paths) {\n            insert(root, path);\n        }\n        //Traverse the treee and delete the nodes\n        mark(root);\n        //again extract the nodes from the tree\n        dfs(root, {});\n        return result;\n    }\n};\n```
[]