Find Duplicate Subtrees - Leetcode Solution

The Find Duplicate Subtrees problem on LeetCode is a Tree problem that requires you to find and return all duplicate subtrees in a binary tree. In this problem, you are given a binary tree, and you are required to return a list of all the duplicate subtrees. A duplicate subtree is a subtree that appears in the original tree at least twice.

Problem Statement

Given the root of a binary tree, return all duplicate subtrees. For each duplicate subtree, you only need to return the root node of any one of them.

Two trees are duplicate if they have the same structure with the same node values.

Example

Input:

     1
    / \
   2   3
  /   / \
 4   2   4
    /
   4

Output:

[2, 4]

Explanation:

There are two duplicate sub-trees:

    2          
   /          
  4          

and

4

Approach

To solve this problem, we can traverse the binary tree in a postorder fashion and store the subtree structure and the frequency of the subtree in a map. We can use a string representation of the subtree structure as the key and a count of the number of times the subtree appears as the value.

We can then traverse the map and find all the duplicate subtrees by checking the frequency of each subtree. Once we find duplicate subtrees, we can add them to a list and return it at the end.

Algorithm

1. Initialize an empty map subtreeCount.
2. Initialize an empty list duplicateSubtrees.
3. Traverse the binary tree in a postorder fashion.
4. For each node in the binary tree, do the following:
   1. If the node is a leaf node, return an empty string.
   2. Get the string representation of the left subtree of the current node.
   3. Get the string representation of the right subtree of the current node.
   4. Get the string representation of the current node's subtree as left_rigth_current.
   5. Increment the frequency of the left_right_current subtree in the subtreeCount map.
5. Traverse the subtreeCount map.
6. For each entry in the subtreeCount map, if the frequency of the subtree is greater than 1:
   1. Add the root node of the subtree to the duplicateSubtrees list.
7. Return the duplicateSubtrees list.

Complexity Analysis

• Time Complexity: O(n^2), where n is the number of nodes in the binary tree. In the worst-case scenario, we may have to visit each node twice, once to calculate the string representation of the subtree and once to update the subtreeCount map.
• Space Complexity: O(n), where n is the number of nodes in the binary tree. We are using a map subtreeCount to store the frequency of each subtree. In the worst-case scenario, we may have to store all the subtrees in the map, which would require O(n) space.

Code

Here's the Python code for the above approach:

def findDuplicateSubtrees(self, root: TreeNode) -> List[TreeNode]:
    def postorder(node):
        if not node:
            return "#"
        left = postorder(node.left)
        right = postorder(node.right)
        subtree = f"{left},{right},{node.val}"
        subtreeCount[subtree] += 1
        if subtreeCount[subtree] == 2:
            duplicateSubtrees.append(node)
        return subtree
    subtreeCount = collections.defaultdict(int)
    duplicateSubtrees = []
    postorder(root)
    return duplicateSubtrees

1