/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * Hashing 
 * Time O(n^2) | Space O(n^2)
 * https://leetcode.com/problems/find-duplicate-subtrees/
 * @param {TreeNode} root
 * @return {TreeNode[]}
 */
var findDuplicateSubtrees = function(root) {
    
    const stringHash = {};

    const makePreOrderStr = (node, str) => {
        if(!node) return str + "-" + "null";
        
        const str1 = makePreOrderStr(node.left, str + "-" + node.val);
        const str2 = makePreOrderStr(node.right, str1);

        return str2;
    }

    const duplicates = [];

    const dfs = (node) => {
        if(!node) return;
        const str = makePreOrderStr(node, "");

        if(!stringHash[str]) {
            stringHash[str] = [];
        }
        
        stringHash[str].push(node);

        dfs(node.left);
        dfs(node.right);
    }   

    dfs(root);
    
    for (let key in stringHash) {
        if(stringHash[key].length > 1) duplicates.push(stringHash[key][0]);
    }

    return duplicates;
};