> For the complete documentation index, see [llms.txt](https://soumyajit4419.gitbook.io/ds-algo/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://soumyajit4419.gitbook.io/ds-algo/binary-tree/problems-related-to-binary-trees/27.-find-duplicate-subtrees.md).

# 27. Find Duplicate Subtrees

Given the `root` of a binary tree, return all **duplicate subtrees**.

For each kind of duplicate subtrees, 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 1:**

![](https://assets.leetcode.com/uploads/2020/08/16/e1.jpg)

```
Input: root = [1,2,3,4,null,2,4,null,null,4]
Output: [[2,4],[4]]
```

**Example 2:**

![](https://assets.leetcode.com/uploads/2020/08/16/e2.jpg)

```
Input: root = [2,1,1]
Output: [[1]]
```

**Example 3:**

![](https://assets.leetcode.com/uploads/2020/08/16/e33.jpg)

```
Input: root = [2,2,2,3,null,3,null]
Output: [[2,3],[3]]
```

## Solution: (Use Serialization)

**Approach:**\
**Two tree are same if they have the same structure  along with same node values.**\
**So we can serialize a tree:**\
    **So same tree have same serialized string and we can use map to store it.**

**Performing Postorder traversal and strong the string of root node as**\
**Node->val , left subtree, right subtree and NULL represented with #**

```cpp
class Solution
{
public:
    unordered_map<string, vector<TreeNode *>> m;

    string serialize(TreeNode *root, string s)
    {

        if (root == NULL)
        {
            return "#";
        }

        string lt = serialize(root->left, s);
        string rt = serialize(root->right, s);

        string res = to_string(root->val) + ',' + lt + ',' + rt;
        m[res].push_back(root);
        return res;
    }
    
    vector<TreeNode *> findDuplicateSubtrees(TreeNode *root)
    {
        vector<TreeNode *> res;
        if (root == NULL)
        {
            return res;
        }
        serialize(root, "");

        for (auto itr = m.begin(); itr != m.end(); itr++)
        {

            if (itr->second.size() > 1)
            {
                res.push_back(itr->second[0]);
            }
        }

        return res;
    }
};
```

**Time Complexity: O(n)**