# Solution For Find Duplicate Subtrees

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:
5. If the node is a leaf node, return an empty string.
6. Get the string representation of the left subtree of the current node.
7. Get the string representation of the right subtree of the current node.
8. Get the string representation of the current node’s subtree as `left_rigth_current`.
9. Increment the frequency of the `left_right_current` subtree in the `subtreeCount` map.
10. Traverse the `subtreeCount` map.
11. For each entry in the `subtreeCount` map, if the frequency of the subtree is greater than 1:
12. Add the root node of the subtree to the `duplicateSubtrees` list.
13. 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:

```python 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```

## Step by Step Implementation For Find Duplicate Subtrees

```/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List findDuplicateSubtrees(TreeNode root) {
List list = new ArrayList<>();
if(root==null)
return list;
Map map = new HashMap<>();
inorder(root, map, list);
return list;
}

public void inorder(TreeNode root, Map map, List list){
if(root==null)
return ;
StringBuffer sb = new StringBuffer();
sb.append(root.val);
sb.append(",");
inorder(root.left, map, list);
sb.append(inorder(root.right, map, list));
String str = sb.toString();
if(map.containsKey(str)){
if(map.get(str)==1)
}
else
map.put(str, 1);
}
}```
```# 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]:
# initialize a dictionary to store values of subtrees
dic = collections.defaultdict(int)
# initialize a list to store duplicate subtrees
output = []

# define a helper function to get values of subtrees
def get_val(node):
# if node is None, return "#"
if not node:
return "#"
# concatenate values of node.val, left subtree and right subtree
# and store it in the dictionary
tree_val = str(node.val) + get_val(node.left) + get_val(node.right)
# if the value is already in the dictionary, increment the count
if tree_val in dic:
dic[tree_val] += 1
# if the value is not in the dictionary, add it to the dictionary
else:
dic[tree_val] = 1
# return the value of the subtree
return tree_val

# call the helper function on the root node
get_val(root)
# iterate through the dictionary
for key, val in dic.items():
# if the value is greater than 1, it is a duplicate subtree
if val > 1:
# append the key to the output list
output.append(key)
# return the output list```
```/**
* Definition for a binary tree node.
* function TreeNode(val) {
*     this.val = val;
*     this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {TreeNode[]}
*/
var findDuplicateSubtrees = function(root) {

};```
```/**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode() : val(0), left(nullptr), right(nullptr) {}
*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
vector findDuplicateSubtrees(TreeNode* root) {
unordered_map m;
vector v;
serialize(root,m,v);
return v;
}
string serialize(TreeNode* root,unordered_map &m,vector &v)
{
if(root==NULL)
return "#";
string s=to_string(root->val)+","+serialize(root->left,m,v)+","+serialize(root->right,m,v);
if(++m[s]==2)
v.push_back(root);
return s;
}
};```
```/**
* Definition for a binary tree node.
* public class TreeNode {
*     public int val;
*     public TreeNode left;
*     public TreeNode right;
*     public TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public IList FindDuplicateSubtrees(TreeNode root) {

//Create a list to store all of the duplicate subtrees
IList duplicates = new List();

//Create a dictionary to store all of the subtrees we have seen
//The key will be the string representation of the tree
//The value will be the number of times we have seen that tree
Dictionary seen = new Dictionary();

//Helper function to get the string representation of a tree
string getTreeString(TreeNode root)
{
//If the tree is null, return the string "null"
if(root == null)
{
return "null";
}

//Otherwise, return the string representation of the tree
//This will be the value of the root node, followed by the string representations
//of the left and right subtrees
return root.val.ToString() + "," + getTreeString(root.left) + "," + getTreeString(root.right);
}

//Helper function to add a tree to our dictionary
{
//Get the string representation of the tree
string treeString = getTreeString(root);

//If we have not seen this tree before, add it to the dictionary with a count of 1
if(!seen.ContainsKey(treeString))
{
}
//Otherwise, increment the count for this tree
else
{
seen[treeString]++;
}
}

//Helper function to check if a tree is a duplicate
bool isDuplicate(TreeNode root)
{
//Get the string representation of the tree
string treeString = getTreeString(root);

//If we have seen this tree before, and its count is greater than 1, it is a duplicate
return seen.ContainsKey(treeString) && seen[treeString] > 1;
}

//Add the root node to our dictionary

//If the root node is a duplicate, add it to our list
if(isDuplicate(root))
{
}

//Recursively check the left and right subtrees
if(root.left != null)
{
if(isDuplicate(root.left))
{
}
}
if(root.right != null)
{
if(isDuplicate(root.right))
{