Javascript remove duplicated subtrees
\nfunction Node (val, parent) {\n    this.val = val\n    this.parent = parent\n    this.children = {}\n}\n\n/**\n * @param {string[][]} paths\n * @return {strin
```\nfunction Node (val, parent) {\n    this.val = val\n    this.parent = parent\n    this.children = {}\n}\n\n/**\n * @param {string[][]} paths\n * @return {string[][]}\n */\nvar deleteDuplicateFolder = function(paths) {\n    \n    //Approach: We can imagine this question as a tree. We want to find all the duplicated subtrees but the root of this subtree can be any value\n    \n    // 1. construct a tree for file structure\n    // 2. traverse the tree and create a subTreeMap of subtree \n    // 2.1. The key is bfsTraversal of the subtree. We replace the current node value in the key with *\n    // 2.2. the value to the key of this map will be array of nodes that have the same preorderTraversal\n    // 3. subTreeMap value has more than 1 element, the subtree structure is the same, we remove this node from it\'s parent\n    // 4. traverse the tree to construct the tree as path array for ans\n    \n    \n    // 1. Construct the tree\n    const root = new Node(null,null)\n    for (const path of paths) {\n        let current = root\n        for (const file of path) {\n            if (!current.children[file]) {\n                \n                current.children[file] = new Node(file,current) // remember the parent, so it\'s easier to remove this node later\n            }\n            current = current.children[file]\n            \n        }\n    }\n    \n    // 2. Construct subTreeMap\n    const subTreeMap = {}\n    function bfsTraversal(node, order) {\n        \n        if (Object.keys(node.children).length === 0) { // return node value at the leaf\n            return node.val\n        }\n        let string = node.val+"," // add current node value\n        Object.keys(node.children).sort().forEach((key) => {\n            string += bfsTraversal(node.children[key], order.slice())+"," // add all subtrees value\n        })\n        if (node.val) {\n            const string2 = string.substring(0,0) + "*" + string.substring(1+node.val.length) // replace current node with *\n            if (!subTreeMap[string2]) subTreeMap[string2] = []\n            subTreeMap[string2].push(node) // store the node value\n        }\n        return string\n    }\n    bfsTraversal(root, [])\n    \n    // 3. Find duplicated subtrees\n    const repeated = Object.values(subTreeMap).filter(array => array.length > 1)\n    if (repeated.length > 0) {\n        repeated.forEach(repeat => {\n            repeat.forEach(node => {\n                delete node.parent.children[node.val] // remove this node from the parent\n            })            \n        })\n    }\n    \n    // 4. Return pruned tree as array\n    const fileArray = []    \n    function generateFileArray(node,fileNames) {\n        if (node.val) {\n            fileNames.push(node.val)\n            fileArray.push(fileNames.slice()) // add sub directory\n        }       \n        Object.keys(node.children).forEach(key => {\n            generateFileArray(node.children[key], fileNames)\n        })\n        fileNames.pop() // backtrack to next directory\n    }\n    generateFileArray(root,[])\n    return fileArray\n};\n\n\n\n```
['Backtracking', 'Tree', 'Breadth-First Search']