[Python] Serialize subtrees + complexity analysis, explained
In this problem we need to use problem constrains, especially this one 1 <= sum(paths[i][j].length) <= 2 * 10^5, which is in fact quite powerful: it means that 
In this problem we need to use problem constrains, especially this one `1 <= sum(paths[i][j].length) <= 2 * 10^5`, which is in fact quite powerful: it means that we can not have very long level tree, so tree in some sense balanced more or less. The idea is to hash all possible subtrees.\n\n1. `dfs1(node)` is recursive function, which will create serialization of tree in special form, for example for tree ` paths = [["a"],["c"],["d"],["a","b"],["c","b"],["d","a"]]`, for root we will have `(a(b())c(b())d(a()))`: the structure is the following: we have  `(a(b())` + `c(b())` + `d(a()))`, where each part is serialization of subtree. This function will return us serialization of **all** non-empty subtrees (if it is empty, we do not need it).\n2. Also in our `Node` structure we have flag `dl`, which says us if node was deleted or not: instead of deleting node it is easier for me to change this flag. So, function `dfs2` used to traverse tree and collect all paths in recursive way. Note, that we collect only paths which were not deleted.\n3. Also we need to create tree (actually we do it in the beginning): we iterate over all `path in sorted(paths)` and attach nodes, like we did in classical trie. Note that we need to sort our paths, so the data for the same folder will be hashed in the same way.\n4. Then we run `dfs1(root)`.\n5. After we run `dfs1`, we have dictionaries of hashes `pattern`, so if we see that for some pattern it happens more than two times, we mark `.dl` field in our trie as `True`: it means, that this node was deleted (lazily)\n6. Finally, we just run `dfs2(root, [])` and return `ans`.\n\n#### Compleixity\nDefine by `M` is total number of elements in `paths[i][j]` for every `i` and `j`. Then if we for the moment we assume that each folder name has `O(1)` length, then we can show that  total length of hashes is `O(M)` as well! The logic is the following: Imagine some node **X** in our tree. Then how many times we will meet it in our pathes is equal to number of nodes in subtree for this node! Now, if we remember than each folder name can be upto `k <= 10` size, then we have complexity `O(M*k)` to build hashes. Also we have the same complexity to run `dfs2`: total length of paths can not be more that it was in the beginning, we removed some of them. Also we have a part where we sort `paths`, it has complexity `O(X*log(T))`, where `X =  sum(paths[i][j].length)` and `T` is length of paths. However it is quite loose bound, and in practice it works very fast, due to fast implementation of sort function in python.\n\nThanks @617280219 for pointing out my error in previous analysis. Indeed, if we consider the case of tree:\n`[a1] -> [a2] -> ... -> [a_sqrt(M)] -> [b1b2...bk]`, then:\n1. Sum of all numbers of elements in `paths[i][j]` will be `1 + 2 + .. + (sqrt(M)+1) = O(M)`.\n2. All hashes will take `k + k + 1 + ... + k + sqrt(M) = M + k*sqrt(M)`, so we have extra `k*sqrt(M)` factor here.\n\nWe can make this example even worse, where we have example for `Omega(M*k)` complexity.\n\n![image](https://assets.leetcode.com/users/images/b8c8d5ce-0183-4405-981b-489d053d96eb_1627224859.226564.png)\n\n\n#### Code\n```python\nclass Node:\n    def __init__(self):\n        self.child = defaultdict(Node)\n        self.dl = False\n\nclass Solution:\n    def deleteDuplicateFolder(self, paths):\n        def dfs1(node):\n            key = "(" + "".join(c + dfs1(node.child[c]) for c in node.child) + ")"\n            if key != "()": pattern[key].append(node)\n            return key\n        \n        def dfs2(node, path):\n            for c in node.child:\n                if not node.child[c].dl:\n                    dfs2(node.child[c], path + [c])\n            if path: ans.append(path[:])\n            \n        pattern, root, ans = defaultdict(list), Node(), []\n        \n        for path in sorted(paths):\n            node = root\n            for c in path: node = node.child[c]\n                \n        dfs1(root)\n        \n        for nodes in pattern.values():\n            if len(nodes) > 1:\n                for i in nodes: i.dl = True\n        \n        dfs2(root, [])\n        return ans\n```\n\nIf you have any questions, feel free to ask. If you like solution and explanations, please **Upvote!**
['Depth-First Search']