# Duplicate subtree

Moderate
0/80
Average time to solve is 25m
Contributed by

## Problem statement

You are given a binary tree. You have to find all the duplicate sub-trees of the binary tree. For every duplicate subtree, you just have to return the root of the sub-tree. Two sub-trees are duplicates or the same if the nodes have the same value and the same structure.

Example:-
``````For the given binary tree: [1, 2, 1, -1, -1, 2, 1, -1, -1, -1, -1]
Start Node: 3

1
/ \
2   1
/ \
2  1

The answer should be [[2]] because the subtree [2] is present 2 times.
``````
Detailed explanation ( Input/output format, Notes, Images )
Constraints :
``````1 <= T <= 5
1 <= N (Number of Nodes) <= 10^5
1 <= VALUE of the nodes <= 10^9

Time Limit = 1 sec
``````
##### Sample Input 1 :
``````2
1 2 3 4 -1 -1 5 -1 -1 -1 -1
1 1 1 -1 -1 -1 -1
``````
##### Sample Output 1 :
``````1
``````
##### Explanation for Sample Output 1 :
``````In the first test case, the tree looks like this:-
``````

``````So, there is no duplicate subtree in the tree given above.

In the second test case, the tree looks like this:-
``````

``````So, the duplicate subtree given is [1].
``````
##### Sample Input 2 :
``````1
2 2 2 3 -1 3 -1 -1 -1 -1 -1
``````
##### Sample Output 2 :
``````3
2 3
``````
Console