Java Solution | Using Trie With PostOrder And InOrder DFS Traversal
Steps :\n\n1. Build a Trie. Here I am using map for the children node because node value is a string, not a single character.\n\n2. PostOrder -  For duplication
Steps :\n\n1. Build a Trie. Here I am using map for the children node because node value is a string, not a single character.\n\n2. PostOrder -  For duplication detection in tree.\n*  The substructure is encoded using \'(\' and \')\' to denote levels e.g. a (b, c,d (...),) \n*  Order of node\'s children is important. For example \'a(b,c)\' vs \'a(c,b)\'. Using TreeMap for node.children.\n*  Record substructure int a map<String, Node> with key is a serialized structure string.\n*  Mark the node.duplicate = true if its substructure has seen earlier.\n\n3. DFS and stop at nodes which node.dup=true.\n```\nclass Solution {\n    private static class Node {\n\t\tprivate String val;\n\t\tprivate boolean duplicate;\n\t\tprivate Map<String, Node> children;\n\n\t\tpublic Node(String val) {\n\t\t\tthis.val = val;\n\t\t\tthis.duplicate = false;\n\t\t\tthis.children = new TreeMap<String, Node>();\n\t\t}\n\t}\n\n\tprivate Node root = new Node("/");\n\n\tprivate String postOrder(Node curr, Map<String, Node> map) {\n\t\tStringBuffer sb = new StringBuffer();\n\t\tfor (Node child : curr.children.values()) {\n\t\t\tsb.append(postOrder(child, map));\n\t\t\tsb.append(",");\n\t\t}\n\n\t\tString key = sb.toString();\n\t\tif (sb.length() == 0) {\n\t\t\treturn curr.val + key; // leaf node\n\t\t}\n\t\tif (map.containsKey(key)) {\n\t\t\tNode orig = map.get(key);\n\t\t\torig.duplicate = true;\n\t\t\tcurr.duplicate = true;\n\t\t} else {\n\t\t\tmap.put(key, curr);\n\t\t}\n\n\t\treturn curr.val + "(" + key + ")";\n\t}\n\n\tprivate void inOrder(List<List<String>> ans, Node node, List<String> list) {\n\t\tif (node == null) {\n\t\t\treturn;\n\t\t}\n\t\tfor (Node child : node.children.values()) {\n\t\t\tif (child.duplicate) {\n\t\t\t\tcontinue;\n\t\t\t}\n\t\t\tlist.add(child.val);\n\t\t\tans.add(new ArrayList<>(list));\n\t\t\tinOrder(ans, child, list);\n\t\t\tlist.remove(list.size() - 1);\n\t\t}\n\t}\n\n\tprivate void insertPath(List<String> path) {\n\t\tNode curr = this.root;\n\t\tfor (String folder : path) {\n\t\t\tif (!curr.children.containsKey(folder)) {\n\t\t\t\tcurr.children.put(folder, new Node(folder));\n\n\t\t\t}\n\t\t\tcurr = curr.children.get(folder);\n\t\t}\n\t}\n\n    public List<List<String>> deleteDuplicateFolder(List<List<String>> paths) {\n        for (List<String> path : paths) {\n\t\t\tinsertPath(path);\n\t\t}\n\t\tMap<String, Node> map = new HashMap<>();\n\t\tpostOrder(this.root, map);\n\t\tList<List<String>> ans = new ArrayList<>();\n\t\tinOrder(ans, this.root, new ArrayList<String>());\n\t\treturn ans;\n    }\n}\n```\nSome Other Problems Using Trie Data Structure \n[1268 : Search Suggestions System](https://leetcode.com/problems/search-suggestions-system/discuss/2638534/java-solution-using-trie-runtime-37-ms-beats-7219)\n[1233 : Remove Sub-Folders from the Filesystem](https://leetcode.com/problems/remove-sub-folders-from-the-filesystem/discuss/2638522/java-solution-using-trie-runtime-43-ms-beats-9605)\n[648\t: Replace Words](https://leetcode.com/problems/replace-words/discuss/2638625/java-solution-using-trie-runtime-14-ms-beats-962219)\n[820\t: Short Encoding of Words](https://leetcode.com/problems/short-encoding-of-words/discuss/2639021/java-solution-using-trie)\n[208\t: Implement Trie (Prefix Tree)](https://leetcode.com/problems/implement-trie-prefix-tree/discuss/2638657/simple-java-solution)\n[386\t: Lexicographical Numbers](https://leetcode.com/problems/lexicographical-numbers/discuss/2639107/java-solution-using-trie)\n[1023 : Camelcase Matching](https://leetcode.com/problems/camelcase-matching/discuss/2639736/java-solution-using-trie)\n[677\t: Map Sum Pairs](https://leetcode.com/problems/map-sum-pairs/discuss/2639994/java-solution-using-trie-and-hashmap)\n[676\t: Implement Magic Dictionary](https://leetcode.com/problems/implement-magic-dictionary/discuss/2640276/java-solution-using-trie)\n[421\t: Maximum XOR of Two Numbers in an Array](https://leetcode.com/problems/maximum-xor-of-two-numbers-in-an-array/discuss/2643276/java-trie-approach-add-number-and-check-its-max-xor-on-fly-tc-on-and-sc-on)\n[792\t: Number of Matching Subsequences](https://leetcode.com/problems/number-of-matching-subsequences/discuss/2643489/java-solutions-two-approach-1-using-trie-2-hashmap)\n[720\t: Longest Word in Dictionary](https://leetcode.com/problems/longest-word-in-dictionary/discuss/2643586/java-solution-using-trie-dfs)\n[2261 : K Divisible Elements Subarrays](https://leetcode.com/problems/k-divisible-elements-subarrays/discuss/2643761/java-solution-sliding-window-trie-runtime-41-ms-faster-than-9846)\n[139\t: Word Break](https://leetcode.com/problems/word-break/discuss/2643915/java-solutions-two-approach-1-using-trie-bfs-2-dp)\n[211\t: Design Add and Search Words Data Structure](https://leetcode.com/problems/design-add-and-search-words-data-structure/discuss/2643839/java-solution-using-trie-dfs)\n[1948 : Delete Duplicate Folders in System](https://leetcode.com/problems/delete-duplicate-folders-in-system/discuss/2646138/java-solution-using-trie-with-postorder-and-inorder-dfs-traversal)\n[1032 : Stream of Characters](https://leetcode.com/problems/stream-of-characters/discuss/2646970/java-solution-using-trie)\n[212. Word Search II](https://leetcode.com/problems/word-search-ii/discuss/2779677/Java-Solution-or-Using-Trie)
['Tree', 'Depth-First Search', 'Trie', 'Java']