# Find Duplicate Subtrees

Difficulty Level Medium
TreeViews 1325

## Duplicate Subtrees

Subtrees are said to be duplicate if they have the same node values and structure. Given a binary tree with n nodes. Find all the duplicate subtrees and return their root node.

## Example

Here, the subtrees 4 and 2->4 appear more than once therefore we will return root nodes of both the subtrees i.e. 4 and 2.

Here, the subtree 4 appears more than once therefore we will return the root node of the sub-tree i.e. 4.

## Using the Hashmap Method

### Algorithm for Find Duplicate Subtrees

1. Initialize a binary tree.
2. Create an unordered map to store string and int types.
3. If the node is null return empty string.
4. Store the values of nodes in a string by converting them to string type.
5. Check if a string value is already present in the map i.e. map[string] is equal to one print the value of the node.
6. Else increment value in the map by 1.
7. Return string.

Time Complexity: O(n^2) where n is the number of nodes in the binary tree. We visit each node once but the creation may take O(n)O(n) work therefore the time complexity is O(n^2).

Space Complexity: O(n^2) is the space used for hashmap and creation of tree.

### C++ Program

```#include <bits/stdc++.h>
using namespace std;

struct Node{
int value;
struct Node* left, *right;
};

string inorder(Node* node, unordered_map<string, int>& m){
if(!node)
return "";

string str = "(";
str += inorder(node->left, m);
str += to_string(node->value);
str += inorder(node->right, m);
str += ")";

if(m[str] == 1)
cout << node->value << " ";

m[str]++;

return str;
}

void Duplicates(Node* root){
unordered_map<string, int> m;
inorder(root, m);
}

Node* newNode(int data){
Node* temp = new Node;
temp->value = data;
temp->left = temp->right = NULL;
return temp;
}

int main(){

Node* root = NULL;
root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->right->left = newNode(2);
root->right->left->left = newNode(4);
root->right->right = newNode(4);
Duplicates(root);

return 0;
}```
`4 2`

### Java Program

```import java.util.HashMap;

class Duplicate_subtress{

static HashMap<String, Integer> m;

static class Node{
int data;
Node left;
Node right;
Node(int data){
this.data = data;
left = null;
right = null;
}
}

static String inorder(Node node){
if(node == null)
return "";

String str = "(";
str += inorder(node.left);
str += Integer.toString(node.data);
str += inorder(node.right);
str += ")";

if(m.get(str) != null && m.get(str)==1 )
System.out.print( node.data + " ");

if(m.containsKey(str))
m.put(str, m.get(str) + 1);
else
m.put(str, 1);

return str;
}

static void Duplicates(Node root){
m = new HashMap<>();
inorder(root);
}

public static void main(String args[]){

Node root = null;
root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
root.left.left = new Node(4);
root.right.left = new Node(2);
root.right.left.left = new Node(4);
root.right.right = new Node(4);
Duplicates(root);

}
}```
`4 2`

References

Translate »