Problem: Find Duplicate Subtrees

This problem asks to find all duplicate subtrees within a given binary tree. Two trees are considered duplicates if they have the same structure and node values. The solution should return a list containing the root node of each unique duplicate subtree.

Approach

The most efficient approach uses Depth-First Search (DFS) and a hash table (or map) to identify duplicate subtrees.

1. Tree Serialization: We need a way to represent each subtree as a unique string. A common technique is to serialize the tree using a pre-order traversal, representing each node as node.val,left_subtree_serialization,right_subtree_serialization. This string uniquely identifies the subtree's structure and values.

2. DFS Traversal: Perform a DFS traversal of the binary tree. For each node, recursively serialize its subtree using the method above.

3. Hash Table (Map): Use a hash table (map) to store the serialized strings as keys and their counts as values. For each serialized string encountered during DFS, increment its count in the hash table. If the count becomes 2, it indicates a duplicate subtree, and its root node is added to the result list.

Time and Space Complexity

• Time Complexity: O(N), where N is the number of nodes in the tree. The DFS traversal visits each node once, and serialization/hash table operations take constant time per node.

• Space Complexity: O(N) in the worst case, to store the serialized strings in the hash table. In the best case, if there are no duplicates, the space complexity is O(log N) (for balanced trees) or O(N) (for skewed trees) to maintain the recursion stack during DFS.

Code Explanation (Python)

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
 
class Solution:
    def findDuplicateSubtrees(self, root: TreeNode) -> List[TreeNode]:
        count = collections.Counter()  # Hash table to store serialized subtrees and counts
        result = [] # list to store the root of the duplicate subtrees
 
        def dfs(node):
            if not node:
                return "#"  # Empty subtree represented by "#"
 
            subtree_str = f"{node.val},{dfs(node.left)},{dfs(node.right)}" # subtree serialization using preorder traversal
 
            count[subtree_str] += 1
            if count[subtree_str] == 2:  # If count becomes 2, it's a duplicate
                result.append(node)
            return subtree_str
 
        dfs(root)
        return result
 

The Python code efficiently implements the described approach. The dfs function recursively serializes subtrees and updates the count dictionary. The result list stores the root nodes of duplicate subtrees as soon as they are identified.

Code in Other Languages

The approach is similar in other languages; the primary difference lies in the syntax for hash tables/maps and string manipulation. The provided code examples in Java, C++, Go, TypeScript, and Rust showcase these adaptations. All of them adhere to the same algorithmic strategy.