# Check if a Binary Tree contains duplicate subtrees of size 2 or more

Given a Binary Tree, check whether the Binary tree contains a duplicate sub-tree of size 2 or more.
Note : Two same leaf nodes are not considered as subtree size of a leaf node is one.

```Input :  Binary Tree
A
/
B        C
/
D     E       B
/
D    E
Output : Yes
```

Asked in : Google Interview Tree with duplicate Sub-Tree [ highlight by blue color ellipse ]

[ Method 1]
A simple solution is that, we pick every node of tree and try to find is any sub-tree of given tree is present in tree which is identical with that sub-tree. Here we can use below post to find if a subtree is present anywhere else in tree.
Check if a binary tree is subtree of another binary tree

[Method 2 ]( Efficient solution )
An Efficient solution based on tree serialization and hashing. The idea is to serialize subtrees as strings and store the strings in hash table. Once we find a serialized tree (which is not a leaf) already existing in hash-table, we return true.
Below The implementation of above idea.

## C++

 `// C++ program to find if there is a duplicate ` `// sub-tree of size 2 or more. ` `#include ` `using` `namespace` `std; ` ` `  `// Separator node ` `const` `char` `MARKER = ``'\$'``; ` ` `  `// Structure for a binary tree node ` `struct` `Node ` `{ ` `    ``char` `key; ` `    ``Node *left, *right; ` `}; ` ` `  `// A utility function to create a new node ` `Node* newNode(``char` `key) ` `{ ` `    ``Node* node = ``new` `Node; ` `    ``node->key = key; ` `    ``node->left = node->right = NULL; ` `    ``return` `node; ` `} ` ` `  `unordered_set subtrees; ` ` `  `// This function returns empty string if tree ` `// contains a duplicate subtree of size 2 or more. ` `string dupSubUtil(Node *root) ` `{ ` `    ``string s = ``""``; ` ` `  `    ``// If current node is NULL, return marker ` `    ``if` `(root == NULL) ` `        ``return` `s + MARKER; ` ` `  `    ``// If left subtree has a duplicate subtree. ` `    ``string lStr = dupSubUtil(root->left); ` `    ``if` `(lStr.compare(s) == 0) ` `       ``return` `s; ` ` `  `    ``// Do same for right subtree ` `    ``string rStr = dupSubUtil(root->right); ` `    ``if` `(rStr.compare(s) == 0) ` `       ``return` `s; ` ` `  `    ``// Serialize current subtree ` `    ``s = s + root->key + lStr + rStr; ` ` `  `    ``// If current subtree already exists in hash ` `    ``// table. [Note that size of a serialized tree ` `    ``// with single node is 3 as it has two marker ` `    ``// nodes. ` `    ``if` `(s.length() > 3 && ` `        ``subtrees.find(s) != subtrees.end()) ` `       ``return` `""``; ` ` `  `    ``subtrees.insert(s); ` ` `  `    ``return` `s; ` `} ` ` `  `// Driver program to test above functions ` `int` `main() ` `{ ` `    ``Node *root = newNode(``'A'``); ` `    ``root->left = newNode(``'B'``); ` `    ``root->right = newNode(``'C'``); ` `    ``root->left->left = newNode(``'D'``); ` `    ``root->left->right = newNode(``'E'``); ` `    ``root->right->right = newNode(``'B'``); ` `    ``root->right->right->right = newNode(``'E'``); ` `    ``root->right->right->left= newNode(``'D'``); ` ` `  `    ``string str = dupSubUtil(root); ` ` `  `    ``(str.compare(``""``) == 0) ? cout << ``" Yes "``: ` `                             ``cout << ``" No "` `; ` `    ``return` `0; ` `} `

## Java

 `// Java program to find if there is a duplicate  ` `// sub-tree of size 2 or more.  ` `import` `java.util.HashSet; ` `public` `class` `Main {  ` ` `  `    ``static` `char` `MARKER = ``'\$'``; ` ` `  `    ``// This function returns empty string if tree  ` `    ``// contains a duplicate subtree of size 2 or more.  ` `    ``public` `static` `String dupSubUtil(Node root, HashSet subtrees)  ` `    ``{  ` `        ``String s = ``""``;  ` `   `  `        ``// If current node is NULL, return marker  ` `        ``if` `(root == ``null``)  ` `            ``return` `s + MARKER;  ` `   `  `        ``// If left subtree has a duplicate subtree.  ` `        ``String lStr = dupSubUtil(root.left,subtrees);  ` `        ``if` `(lStr.equals(s))  ` `            ``return` `s;  ` `   `  `        ``// Do same for right subtree  ` `        ``String rStr = dupSubUtil(root.right,subtrees);  ` `        ``if` `(rStr.equals(s))  ` `            ``return` `s;  ` `   `  `        ``// Serialize current subtree  ` `        ``s = s + root.data + lStr + rStr;  ` `   `  `        ``// If current subtree already exists in hash  ` `        ``// table. [Note that size of a serialized tree  ` `        ``// with single node is 3 as it has two marker  ` `        ``// nodes.  ` `        ``if` `(s.length() > ``3` `&& subtrees.contains(s))  ` `            ``return` `""``;  ` `   `  `        ``subtrees.add(s);  ` `        ``return` `s;  ` `    ``}  ` ` `  `    ``//Function to find if the Binary Tree contains duplicate  ` `    ``//subtrees of size 2 or more ` `    ``public` `static` `String dupSub(Node root) ` `    ``{ ` `        ``HashSet subtrees=``new` `HashSet<>(); ` `        ``return` `dupSubUtil(root,subtrees); ` `    ``} ` ` `  `    ``public` `static` `void` `main(String args[])  ` `    ``{ ` `        ``Node root = ``new` `Node(``'A'``);  ` `        ``root.left = ``new` `Node(``'B'``);  ` `        ``root.right = ``new` `Node(``'C'``);  ` `        ``root.left.left = ``new` `Node(``'D'``);  ` `        ``root.left.right = ``new` `Node(``'E'``);  ` `        ``root.right.right = ``new` `Node(``'B'``);  ` `        ``root.right.right.right = ``new` `Node(``'E'``);  ` `        ``root.right.right.left= ``new` `Node(``'D'``);  ` `        ``String str = dupSub(root);  ` `        ``if``(str.equals(``""``)) ` `            ``System.out.print(``" Yes "``); ` `        ``else`     `            ``System.out.print(``" No "``);  ` `    ``} ` `} ` ` `  `// A binary tree Node has data,  ` `// pointer to left child  ` `// and a pointer to right child  ` `class` `Node {  ` `    ``int` `data;  ` `    ``Node left,right;  ` `    ``Node(``int` `data) ` `    ``{ ` `        ``this``.data=data; ` `    ``} ` `}; ` `//This code is contributed by Gaurav Tiwari `

## C#

 `// C# program to find if there is a duplicate  ` `// sub-tree of size 2 or more. ` `using` `System; ` `using` `System.Collections.Generic; ` ` `  `class` `GFG  ` `{  ` ` `  `    ``static` `char` `MARKER = ``'\$'``; ` ` `  `    ``// This function returns empty string if tree  ` `    ``// contains a duplicate subtree of size 2 or more.  ` `    ``public` `static` `String dupSubUtil(Node root,  ` `                    ``HashSet subtrees)  ` `    ``{  ` `        ``String s = ``""``;  ` `     `  `        ``// If current node is NULL, return marker  ` `        ``if` `(root == ``null``)  ` `            ``return` `s + MARKER;  ` `     `  `        ``// If left subtree has a duplicate subtree.  ` `        ``String lStr = dupSubUtil(root.left,subtrees);  ` `        ``if` `(lStr.Equals(s))  ` `            ``return` `s;  ` `     `  `        ``// Do same for right subtree  ` `        ``String rStr = dupSubUtil(root.right,subtrees);  ` `        ``if` `(rStr.Equals(s))  ` `            ``return` `s;  ` `     `  `        ``// Serialize current subtree  ` `        ``s = s + root.data + lStr + rStr;  ` `     `  `        ``// If current subtree already exists in hash  ` `        ``// table. [Note that size of a serialized tree  ` `        ``// with single node is 3 as it has two marker  ` `        ``// nodes.  ` `        ``if` `(s.Length > 3 && subtrees.Contains(s))  ` `            ``return` `""``;  ` `     `  `        ``subtrees.Add(s);  ` `        ``return` `s;  ` `    ``}  ` ` `  `    ``// Function to find if the Binary Tree contains   ` `    ``// duplicate subtrees of size 2 or more ` `    ``public` `static` `String dupSub(Node root) ` `    ``{ ` `        ``HashSet subtrees = ``new` `HashSet(); ` `        ``return` `dupSubUtil(root,subtrees); ` `    ``} ` ` `  `    ``// Driver code ` `    ``public` `static` `void` `Main(String []args)  ` `    ``{ ` `        ``Node root = ``new` `Node(``'A'``);  ` `        ``root.left = ``new` `Node(``'B'``);  ` `        ``root.right = ``new` `Node(``'C'``);  ` `        ``root.left.left = ``new` `Node(``'D'``);  ` `        ``root.left.right = ``new` `Node(``'E'``);  ` `        ``root.right.right = ``new` `Node(``'B'``);  ` `        ``root.right.right.right = ``new` `Node(``'E'``);  ` `        ``root.right.right.left= ``new` `Node(``'D'``);  ` `        ``String str = dupSub(root);  ` `        ``if``(str.Equals(``""``)) ` `            ``Console.Write(``" Yes "``); ` `        ``else` `            ``Console.Write(``" No "``);  ` `    ``} ` `} ` ` `  `// A binary tree Node has data,  ` `// pointer to left child  ` `// and a pointer to right child  ` `public` `class` `Node  ` `{  ` `    ``public` `int` `data;  ` `    ``public` `Node left,right;  ` `    ``public` `Node(``int` `data) ` `    ``{ ` `        ``this``.data = data; ` `    ``} ` `}; ` ` `  `// This code is contributed by 29AjayKumar `

Output:

```Yes
```

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.

This article is attributed to GeeksforGeeks.org

## tags:

Tree Google Google Tree

code

load comments