Find Duplicate Subtrees

class Solution {
public:
    vector<TreeNode*> getDuplicateSubtrees(TreeNode* root) {
        unordered_map<string, int> serializedToId;
        unordered_map<int, int> subtreeCount;
        vector<TreeNode*> duplicates;
        function<int(TreeNode*)> encode = [&serializedToId, &subtreeCount, &duplicates,
                                           &encode](TreeNode* node) -> int {
            if (node == nullptr) {
                return 0;
            }
            string serialized = to_string(encode(node->left)) + "," + to_string(node->val) + "," +
                                to_string(encode(node->right));
            if (serializedToId.find(serialized) == serializedToId.end()) {
                serializedToId[serialized] = serializedToId.size() + 1;
            }
            int uid = serializedToId[serialized];
            subtreeCount[uid]++;
            if (subtreeCount[uid] == 2) {
                duplicates.push_back(node);
            }
            return uid;
        };
        encode(root);
        return duplicates;
    }
};

This C++ solution addresses the problem of finding all duplicate subtrees in a binary tree. Each subtree is serialized into a string form to allow for comparison. Here's a breakdown of how the code functions:

1. The function getDuplicateSubtrees receives the root node of a binary tree.
2. An unordered map, serializedToId, maps a serialized subtree to a unique identifier.
3. Another unordered map, subtreeCount, keeps track of how many times each unique serialized subtree appears.
4. A vector, duplicates, is used to store the root nodes of subtrees that are found to be duplicates.
5. The internal encode function defines the mechanism for recursive subtree serialization:
   • If the node is nullptr, it returns 0, indicating an empty subtree.
   • It recursively serializes the subtree using preorder traversal (node, left, right) and combines these into a string.
   • If the serialized string is not already a key in serializedToId, it adds it with a new unique identifier.
   • It then checks if this particular serialized form has been encountered before by using the subtreeCount map.
   • If a serialized subtree is encountered twice, it is added to the duplicates vector.
   • Each call to encode returns a unique identifier corresponding to the serialized subtree of the node.
6. The encode function is initially called with the root of the tree.
7. Finally, the duplicates vector, containing all the duplicate subtrees' root nodes, is returned.

By serializing subtrees and mapping these to unique identifiers, this solution efficiently identifies and collects roots of all duplicate subtrees in a binary tree. It leverages hashing (via unordered maps) to manage and compare subtree structures effectively.

class Solution {
    public List<TreeNode> getDuplicateSubtrees(TreeNode root) {
        List<TreeNode> duplicates = new LinkedList<>();
        searchDuplicates(root, new HashMap<>(), new HashMap<>(), duplicates);
        return duplicates;
    }
    
    public int searchDuplicates(TreeNode node, Map<String, Integer> subtreeMap,
            Map<Integer, Integer> countMap, List<TreeNode> duplicates) {
        if (node == null) {
            return 0;
        }
        String serial = searchDuplicates(node.left, subtreeMap, countMap, duplicates) + "," + node.val +
                "," + searchDuplicates(node.right, subtreeMap, countMap, duplicates);
        if (!subtreeMap.containsKey(serial)) {
            subtreeMap.put(serial, subtreeMap.size() + 1);
        }
        int subtreeId = subtreeMap.get(serial);
        countMap.put(subtreeId, countMap.getOrDefault(subtreeId, 0) + 1);
        if (countMap.get(subtreeId) == 2) {
            duplicates.add(node);
        }
        return subtreeId;
    }
}

In this Java solution, the task is to find all duplicate subtrees in a given binary tree. Each subtree is serialized into a string format and stored alongside its occurrence count using hash maps. This method not only identifies duplicates efficiently but also stores references to the original subtree roots where the duplicates start.

The implementation involves two primary methods:

1. getDuplicateSubtrees(TreeNode root): This method initializes necessary data structures and triggers the recursive search through the binary tree to locate and collect duplicates.

2. searchDuplicates(TreeNode node, Map subtreeMap, Map countMap, List<TreeNode> duplicates): This recursive function:

   • Serializes the current subtree rooted at node.
   • Tracks the serialization in subtreeMap to ensure each unique subtree gets a unique ID.
   • Records the frequency of each subtree ID in countMap.
   • Checks the count of each serialization; if a serialization appears exactly twice, it adds the root node of that subtree to the duplicates list. This ensures each duplicate subtree is only added once.
   • Finally, returns the unique subtree ID, facilitating serialization of parent trees.

The solution efficiently catalogs and checks for duplicates using serialization and mapping strategies, ensuring that duplicates are identified based on structural equality rather than object references. This approach provides a robust and scalable method to solve the problem of finding duplicate subtrees in binary trees.

class Solution:
    def findRepeatedSubtrees(self, root):
        def dfs(node):
            if not node:
                return "#"
            sub_tree = (dfs(node.left), node.val, dfs(node.right))
            if sub_tree not in tree_map:
                tree_map[sub_tree] = len(tree_map) + 1
            subtree_id = tree_map[sub_tree]
            counter[subtree_id] += 1
            if counter[subtree_id] == 2:
                result.append(node)
            return subtree_id
    
        tree_map = {}
        counter = collections.defaultdict(int)
        result = []
        dfs(root)
        return result

The provided Python script defines a method to find duplicate subtrees within a binary tree. Each subtree that appears more than once with the same structure and node values is considered duplicate. The solution employs a depth-first search (DFS) to examine each node's subtree and utilizes a tuple to represent the structure and values of these subtrees. Note the use of serialization techniques where the subtrees are converted into a serialized string format represented by tuples.

The following explains the critical components and steps of the algorithm:

• Define a helper function dfs() which is a recursive function to traverse the tree in a depth-first manner.
• For each node encountered, it identifies a unique signature (a tuple) that represents the subtree structure rooted at that node. This tuple includes the node's value and the identifiers of the left and right subtrees.
• Use a dictionary tree_map to map each unique subtree structure to a unique identifier.
• Employ another dictionary counter to count the occurrences of each subtree identifier.
• If a subtree's count in counter reaches two — indicating the subtree has been seen once before — it adds the subtree's root node to the result list result.
• Finally, return the result list, which contains the root nodes of all duplicate subtrees.

This approach ensures that each subtree is only recorded once when it first becomes a duplicate, optimizing the process and avoiding redundancy.