# Google Interview find if a given binary tree has duplicate sub trees or not

Find if a given binary tree has duplicate sub trees or not.
(Two leaf nodes of a parent do not count as subtree)

Our tree will be like below.

Algorithm

```import java.util.Set;
import java.util.TreeSet;

import com.omt.learn.algo.util.tree.TreeNode;

public class DuplicateTreeInTree {

public static void main(String[] args) {
System.out.println("Is Duplicate Sub Trees :" + isContainsDuplicateTrees(generateTree()));
}

public static boolean isContainsDuplicateTrees(TreeNode root) {

return isContainsDuplicateTrees(new TreeSet<>(), root);
}

public static boolean isContainsDuplicateTrees(Set<String> trees, TreeNode root) {

if (root != null) {
String tree = "";
if (root.leftNode != null) {
tree += root.leftNode.nodeName;
}

tree += root.nodeName;

if (root.rightNode != null) {
tree += root.rightNode.nodeName;
}

if (trees.contains(tree)) {
System.out.println(tree);
return true;
}
if (tree.length() == 3) {
System.out.println(tree);
}
boolean isLeftHave = false;
if (root.leftNode != null) {
isLeftHave = isContainsDuplicateTrees(trees, root.leftNode);
}

boolean isRightHave = false;
if (root.rightNode != null) {
isRightHave = isContainsDuplicateTrees(trees, root.rightNode);
}

return (isLeftHave || isRightHave);

}
return false;
}

public static TreeNode generateTree() {
TreeNode AVL = new TreeNode(new TreeNode(new TreeNode("D"), new TreeNode("E"), "B"),
new TreeNode(new TreeNode("I"),
new TreeNode(new TreeNode("H"), new TreeNode(new TreeNode("D"), new TreeNode("E"), "B"), "F"),
"C"),
"A");
return AVL;
}
}
```

TreeNode.java

```public class TreeNode {

public String nodeName = "";
public boolean isVisited = false;
public int value = 0;
public TreeNode leftNode = null;
public TreeNode rightNode = null;
public TreeNode parentNode = null;

public TreeNode() {
// TODO Auto-generated constructor stub
}

public TreeNode(String name) {
nodeName = name;
}

public TreeNode(TreeNode left, TreeNode right, String name) {
leftNode = left;
rightNode = right;
nodeName = name;
setParent();
}

private void setParent() {
if (leftNode != null) {
leftNode.parentNode = this;
}

if (rightNode != null) {
rightNode.parentNode = this;
}
}

}
```