## Similar Problems

Similar Problems not available

# Find Duplicate Subtrees - Leetcode Solution

LeetCode: Find Duplicate Subtrees Leetcode Solution

Difficulty: Medium

Topics: hash-table tree binary-tree depth-first-search

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

- Initialize an empty map
`subtreeCount`

. - Initialize an empty list
`duplicateSubtrees`

. - Traverse the binary tree in a postorder fashion.
- For each node in the binary tree, do the following:
- If the node is a leaf node, return an empty string.
- Get the string representation of the left subtree of the current node.
- Get the string representation of the right subtree of the current node.
- Get the string representation of the current node's subtree as
`left_rigth_current`

. - Increment the frequency of the
`left_right_current`

subtree in the`subtreeCount`

map.

- Traverse the
`subtreeCount`

map. - For each entry in the
`subtreeCount`

map, if the frequency of the subtree is greater than 1:- Add the root node of the subtree to the
`duplicateSubtrees`

list.

- Add the root node of the subtree to the
- 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
```

## Find Duplicate Subtrees Solution Code

`1`