> For the complete documentation index, see [llms.txt](https://mayanktyagi3111.gitbook.io/interview-prep/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://mayanktyagi3111.gitbook.io/interview-prep/trees/find-duplicate-subtrees.md).

# Find Duplicate Subtrees

Given 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 same node values.

**Example 1:**

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

The following are two duplicate subtrees:

```
      2
     /
    4
```

and

```
    4
```

Therefore, you need to return above trees' root in the form of a list.

```java
class Solution {
    Map<String, Integer> map;
    List<TreeNode> ans;

    public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
        ans = new LinkedList<>();
        map = new HashMap<>();
        postorder(root);
        return ans;
    }

    public String postorder(TreeNode root) {
        if (root == null)
            return "#";
        // Converting tree to post-order comma seprated string
        String serial = postorder(root.left) + "," + postorder(root.right) + "," + root.val;
        if (map.getOrDefault(serial, 0) == 1)
            ans.add(root);
        map.put(serial, map.getOrDefault(serial, 0) + 1);
        return serial;
    }
}
```